jeudi 19 mars 2020

How to solve Atcoder dp task grid problem dynammic programming?

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