fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int MOD = 1e9 + 7; 
  11. const int N = 2e3 + 5; 
  12.  
  13. int add(int a, int b) {
  14. 	return (a + b) % MOD; 
  15. }
  16.  
  17. int n, m;  
  18. string s[N]; 
  19. int dp[N][N]; // dp[i][j] = số cách để quân hậu đi từ ô (1, 1) đến ô (i, j)
  20. int pref_row[N][N], pref_col[N][N], pref_diag[N][N];  
  21.  
  22. int main() {
  23. 	ios::sync_with_stdio(0); cin.tie(0);  	
  24. 	cin >> n >> m;  
  25. 	for (int i = 1; i <= n; i++) {
  26. 		cin >> s[i]; 
  27. 		s[i] = ' ' + s[i]; 
  28. 	}
  29.  
  30. 	// naive dp
  31. 	// dp[1][1] = (s[1][1] == '.');   
  32.  
  33. 	// for (int i = 1; i <= n; i++) {
  34. 	// 	for (int j = 1; j <= m; j++) {
  35. 	// 		// same row
  36. 	// 		for (int k = j - 1; k >= 1; k--) {
  37. 	// 			if (s[i][k] == '#') break; 
  38. 	// 			dp[i][j] = add(dp[i][j], dp[i][k]); 
  39. 	// 		}
  40. 	// 		// same col
  41. 	// 		for (int k = i - 1; k >= 1; k--) {
  42. 	// 			if (s[k][j] == '#') break; 
  43. 	// 			dp[i][j] = add(dp[i][j], dp[k][j]);  
  44. 	// 		}
  45. 	// 		// same diag
  46. 	// 		for (int k = 1; k < min(i, j); k++) {
  47. 	// 			if (s[i - k][j - k] == '#') break; 
  48. 	// 			dp[i][j] = add(dp[i][j], dp[i - k][j - k]); 
  49. 	// 		}
  50. 	// 	}
  51. 	// }
  52.  
  53. 	// optimized-dp using prefix sum
  54. 	dp[1][1] = (s[1][1] == '.');  
  55. 	pref_row[1][1] = pref_col[1][1] = pref_diag[1][1] = dp[1][1];  
  56.  
  57. 	for (int i = 1; i <= n; i++) {
  58. 		for (int j = 1; j <= m; j++) {
  59. 			if (s[i][j] == '#') continue;  
  60. 			// same row 
  61. 			dp[i][j] = add(dp[i][j], pref_row[i][j - 1]); 
  62. 			// same col 
  63. 			dp[i][j] = add(dp[i][j], pref_col[i - 1][j]); 
  64. 			// same diag 
  65. 			dp[i][j] = add(dp[i][j], pref_diag[i - 1][j - 1]); 
  66.  
  67. 			// update prefix sum  
  68. 			pref_row[i][j] = add(pref_row[i][j - 1], dp[i][j]);  
  69. 			pref_col[i][j] = add(pref_col[i - 1][j], dp[i][j]);   
  70. 			pref_diag[i][j] = add(pref_diag[i - 1][j - 1], dp[i][j]); 
  71. 		}
  72. 	}
  73. 	cout << dp[n][m] << '\n'; 
  74. }
Success #stdin #stdout 0.01s 9784KB
comments (?)
stdin
copy 
8 10
..........
..........
..........
..........
..........
..........
..........
..........
stdout
copy 
13701937
https://ideone.com/AFqrDH
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!