josiftepe

Untitled

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