josiftepe

Untitled

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