Advertisement
Josif_tepe

Untitled

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