fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e3 + 5;  
  12. const int MOD = 1e9 + 7;  
  13.  
  14. void add(int& a, int b) {
  15. 	a += b; 
  16. 	if (a >= MOD) a -= MOD; 
  17. }
  18.  
  19. int n;  
  20. string grid[N];  
  21.  
  22. bool inside(int x, int y) {
  23. 	return (1 <= x && x <= n && 1 <= y && y <= n);  
  24. }
  25.  
  26. int dp[N][N]; // dp[x][y] = Số cách đi từ ô (1, 1) đến ô (x, y)
  27.  
  28. int main() {
  29. 	ios::sync_with_stdio(false); 
  30. 	cin.tie(nullptr);  	
  31. 	cin >> n;   
  32.  
  33. 	for (int x = 1; x <= n; x++) {
  34. 		cin >> grid[x];  
  35. 		grid[x] = ' ' + grid[x]; 
  36. 	}
  37.  
  38. 	for (int x = 1; x <= n; x++) {
  39. 		for (int y = 1; y <= n; y++) {
  40. 			int& cur = dp[x][y]; 
  41. 			if (grid[x][y] == '*') {
  42. 				cur = 0; 
  43. 				continue; 
  44. 			}
  45. 			if (x == 1 && y == 1) {
  46. 				cur = 1;
  47. 				continue; 
  48. 			}
  49. 			cur = 0;
  50. 			if (inside(x - 1, y)) {
  51. 				add(cur, dp[x - 1][y]); 
  52. 			}
  53. 			if (inside(x, y - 1)) {
  54. 				add(cur, dp[x][y - 1]); 
  55. 			}
  56. 		}
  57. 	}
  58.  
  59. 	cout << dp[n][n] << '\n'; 
  60. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
4
....
.*..
...*
*...
stdout
copy 
3
https://ideone.com/KnYW3G
language:
C++14 (gcc 8.3)
created:
19 days 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!