Advertisement
Rohit4Pal

Untitled

Jul 27th, 2021
836
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define vc vector<char>
  4. #define vb vector<bool>
  5. #define vi vector<int>
  6. #define mod 1000000007
  7.  
  8. class Grid{
  9.     int m,n;
  10.     int row[2]={1,0};
  11.     int col[2]={0,1};
  12. public:
  13.  
  14.     bool isValid(int i,int j){
  15.         return i>=0 && j>=0 && i<m && j<n;
  16.     }
  17.     int waysToReachEnd(vector<vc> arr){
  18.  
  19.         m=arr.size(),n=arr[0].size();
  20.         vector<vi> dp(m,vi(n,-1));
  21.         vector<vb> visited(m,vb(n,false));
  22.         visited[0][0]=true;
  23.         topDownApproach(arr,dp,0,0,visited);
  24.        
  25.         return dp[0][0];
  26.     }
  27.     int topDownApproach(vector<vc> arr,vector<vi> &dp,int i,int j,vector<vb> &visited){
  28.  
  29.         //base case
  30.         if(i==m-1 && j==n-1)    return 1;
  31.         if(i>=m || j>=n)        return 0;
  32.         if(dp[i][j] != -1)      return dp[i][j];
  33.         if(arr[i][j]=='#')      { dp[i][j]=0;return 0;}
  34.  
  35.         long long ways=0;
  36.         for(int k=0;k<2;k++){
  37.             int x=i+row[k],y=j+col[k];
  38.             if(isValid(x,y) && !visited[x][y] && arr[x][y] != '#'){
  39.                 visited[x][y]=true;
  40.                 ways+=(long long)topDownApproach(arr,dp,x,y,visited);
  41.                 ways%=mod;
  42.                 visited[x][y]=false;
  43.             }
  44.         }
  45.         dp[i][j]=(int)ways;
  46.         return dp[i][j];
  47.     }
  48.  
  49. };
  50. int main(){
  51.  
  52.     int h,w;
  53.     cin>>h>>w;
  54.  
  55.     vector<vc> arr(h,vc(w,0));
  56.     for(auto &i:arr)
  57.         for(auto &j:i)
  58.             cin>>j;
  59.  
  60.     Grid grid;
  61.     cout<<grid.waysToReachEnd(arr);
  62. }
  63.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement