Advertisement
Josif_tepe

Untitled

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