Untitled
unknown
c_cpp
4 years ago
1.0 kB
3
Indexable
#include <iostream> #include <cmath> #include <algorithm> using namespace std; const int MOD = 1000000007; int n; char mat[1005][1005]; int memo[1005][1005]; int main() { cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin >> mat[i][j]; memo[i][j] = 0; } } if(mat[0][0] == '*') { cout << 0 << endl; } else { memo[0][0] = 1; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(i + 1 < n and mat[i + 1][j] != '*') { memo[i + 1][j] += memo[i][j]; memo[i + 1][j] %= MOD; } if(j + 1 < n and mat[i][j + 1] != '*') { memo[i][j + 1] += memo[i][j]; memo[i][j + 1] %= MOD; } } } cout << memo[n - 1][n - 1] << endl; } return 0; } /* f(i, j) --> f(i, j + 1); f(i + 1, j) i == n - 1 && j == n - 1 return 1; .... .*.. ...* *... **/
Editor is loading...