Josif_tepe

Untitled

Jan 30th, 2026
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. using namespace std;
  5. const int maxn = 1050;
  6. const int MOD = 1e9 + 7;
  7. char mat[maxn][maxn];
  8. int n, m;
  9. int dp[maxn][maxn];
  10. int rec(int i, int j) {
  11.     if(i == n - 1 and j == m - 1) {
  12.         return 1;
  13.     }
  14.    
  15.     if(dp[i][j] != -1) {
  16.         return dp[i][j];
  17.     }
  18.    
  19.     int res = 0;
  20.     if(i + 1 < n and mat[i + 1][j] != '#') {
  21.         res += rec(i + 1, j);
  22.         res %= MOD;
  23.     }
  24.    
  25.     if(j + 1 < m and mat[i][j + 1] != '#') {
  26.         res += rec(i, j + 1);
  27.         res %= MOD;
  28.     }
  29.    
  30.     dp[i][j] = res;
  31.     return res;
  32. }
  33. int main() {
  34.     for(int i = 0; i < maxn; i++) {
  35.         for(int j = 0; j < maxn; j++) {
  36.             dp[i][j] = -1;
  37.         }
  38.     }
  39.    
  40.     cin >> n >> m;
  41.     for(int i = 0; i < n; i++) {
  42.         for(int j = 0; j < m; j++) {
  43.             cin >> mat[i][j];
  44.         }
  45.     }
  46.    
  47.     cout << rec(0, 0) << endl;
  48.    
  49.    
  50.     return 0;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment