Josif_tepe

Untitled

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