Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define vc vector<char>
- #define vb vector<bool>
- #define vi vector<int>
- #define mod 1000000007
- class Grid{
- int m,n;
- int row[2]={1,0};
- int col[2]={0,1};
- public:
- bool isValid(int i,int j){
- return i>=0 && j>=0 && i<m && j<n;
- }
- int waysToReachEnd(vector<vc> arr){
- m=arr.size(),n=arr[0].size();
- vector<vi> dp(m,vi(n,-1));
- vector<vb> visited(m,vb(n,false));
- visited[0][0]=true;
- topDownApproach(arr,dp,0,0,visited);
- return dp[0][0];
- }
- int topDownApproach(vector<vc> arr,vector<vi> &dp,int i,int j,vector<vb> &visited){
- //base case
- if(i==m-1 && j==n-1) return 1;
- if(i>=m || j>=n) return 0;
- if(dp[i][j] != -1) return dp[i][j];
- if(arr[i][j]=='#') { dp[i][j]=0;return 0;}
- long long ways=0;
- for(int k=0;k<2;k++){
- int x=i+row[k],y=j+col[k];
- if(isValid(x,y) && !visited[x][y] && arr[x][y] != '#'){
- visited[x][y]=true;
- ways+=(long long)topDownApproach(arr,dp,x,y,visited);
- ways%=mod;
- visited[x][y]=false;
- }
- }
- dp[i][j]=(int)ways;
- return dp[i][j];
- }
- };
- int main(){
- int h,w;
- cin>>h>>w;
- vector<vc> arr(h,vc(w,0));
- for(auto &i:arr)
- for(auto &j:i)
- cin>>j;
- Grid grid;
- cout<<grid.waysToReachEnd(arr);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement