The question: https://atcoder.jp/contests/dp/tasks/dp_h
My approach is below. What I have done is if I can move only right and downward direction to reach to (H,W) from (1,1), then I can move only towards left and upward direction to reach to (1,1) from (H,W). The number of paths will be same. I have defined DP state dp[i][j]= dp[i+1][j] + dp[i][j+1] i.e sum of number of paths coming from right adjacent and down adjacent is the number of ways I can reach dp[i][j] from H,W.
I have initially declared all as zero. Beyond ob1 there is no path upward for last column. Similarly for last row there is no path towards left beyond ob2. where am i going wrong?
#include<bits/stdc++.h>
using namespace std;
typedef long long int lt;
int main()
{
int H, W;
cin>>H>>W;
char grid[H][W];
lt dp[H][W];
lt ob1=0, ob2=0;
memset(dp, 0, sizeof(dp));
for(lt i=0; i<H; i++)
{
for(lt j=0; j<W; j++)
{
cin>>grid[i][j];
if(i==(H-1) && grid[i][j]=='#' )
ob1 = j;
if(j==(W-1) && grid[i][j]=='#' )
ob2 = i;
}
}
// cout<<ob1<<" "<<ob2<<endl;
// cout<<"Printing the grid"<<endl;
/* for(int i=0; i<H; i++)
{
for(lt j=0; j<W; j++)
{
cout<<grid[i][j]<<" ";
}
cout<<endl;
}*/
//cout<<"Calculating the dp array now "<<endl;
for(lt i=H-1;i>=0; i--)
{
for(lt j=W-1; j>=0 ; j--)
{
if(i== (H-1) && grid[i][j]!= '#')
{
if(j<ob1)
dp[i][j]=0;
else
dp[i][j]=1;
}
else if (j== (W-1) && grid[i][j] != '#')
{
if(i<ob2)
dp[i][j]=0;
else
dp[i][j]=1;
}
else if(grid[i][j] != '#')
{
dp[i][j] = dp[i+1][j]+ dp[i][j+1];
}
}
}
/*cout<<"dp array has been calculated"<<endl;
cout<<"Printing the dp array"<<endl;
for(int i=0; i<H; i++)
{
for(lt j=0; j<W; j++)
{
cout<<dp[i][j]<<"\t";
}
cout<<endl;
}*/
cout<<dp[0][0]%1000000007<<endl;
return 0;
}
Aucun commentaire:
Enregistrer un commentaire