fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct matrx{
  4. 	int u = 0, l = 0;
  5. };
  6. int main() {
  7. 	int m, n; cin >> m >> n;
  8. 	char a[2005][2005];
  9. 	matrx dp[2005][2005];
  10. 	matrx cnt[2005][2005];
  11. 	vector<int> dr[2005];
  12. 	vector<int> rr[2005];
  13. 	for(int i = 1; i <= m; i++){
  14. 		for(int j = 1; j <= n; j++){
  15. 			cin >> a[i][j];
  16. 			cnt[i][j].u = cnt[i - 1][j].u + (a[i][j] == 'R'); 
  17. 			cnt[i][j].l = cnt[i][j - 1].l + (a[i][j] == 'R'); 
  18. 			if(a[i][j] == 'R'){
  19. 				dr[i].push_back(j);
  20. 				rr[j].push_back(i);
  21. 			} 
  22. 		}
  23. 	}
  24.  
  25. 	int cntt = 0;
  26. 	for(int i = 1; i <= n; i++){
  27. 		if(a[1][i] == 'R') cntt++;
  28. 		if(cntt > n - i) break;
  29. 		dp[1][i].l = 1;
  30. 	}
  31. 	cntt = 0;
  32. 	for(int i = 2; i <= m; i++){
  33. 		if(a[i][1] == 'R') cntt++;
  34. 		if(cntt > m - i) break;
  35. 		dp[i][1].u = 1;
  36. 	}
  37.  
  38. 	for(int i = 2; i <= m; i++){
  39. 		for(int j = 2; j <= n; j++){
  40. 			int r = cnt[i][n].l - cnt[i][j].l, d = cnt[m][j].u - cnt[i][j].u;
  41. 			dp[i][j].u = dp[i - 1][j].u + dp[i - 1][j].l - (m - i + 1 < d + cnt[i][j].u ? dr[i][cnt[i][j].u - d]:0);
  42. 			dp[i][j].l = dp[i][j - 1].u + dp[i][j - 1].l - (n - j + 1 < r + cnt[i][j].l ? rr[cnt[i][j].l - r][j]:0);
  43.  
  44. 		}
  45.  
  46. 	}
  47. 	for(int i = 1; i <= m; i++){
  48. 		for(int j = 1; j <= n; j++){
  49. 			cout << dp[i][j].u << " " << dp[i][j].l << " ";
  50. 		}
  51. 		cout << endl;
  52. 	}
  53. 	cout << dp[m][n].u + dp[m][n].l;
  54.  
  55.  
  56. 	return 0;
  57. }
Success #stdin #stdout 0.01s 66556KB
comments (?)
stdin 
2 3
...
..R
stdout 
0 1 0 1 0 1 
1 0 1 1 1 2 
3
https://ideone.com/9zI4xs
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!