ABC183_E Queen on Grid

E - Queen on Grid

Overall Solution

You can solve this problem by dynamic programming, because if the place of Queen was decided, you can determine the number of cases of the situation and that of visiting goal from that place, uniquely. You can memorize the number of cases when Queen is in (i,j) as dp[i][j], and do the transition like:

dp[i][j]=dp[i-1][j]+dp[i-2][j]+...+dp[i][j-1]+dp[i][j-2]+...+dp[i-1][j-1]+dp[i-2][j-2]+...

But the time complexity of this solution is O(HW(H+W)), so the time limit will be exceeded.

You can make time complexity lower by using cumulative sum. Define X[i][j],Y[i][j],Z[i][j] as:

X[i][j]=dp[i][j-1]+dp[i][j-2]+...
Y[i][j]=dp[i-1][j]+dp[i-2][j]+...
Z[i][j]=dp[i-1][j-1]+dp[i-2][j-2]+...

then, the transition can be represented as:

(when(i,j) is '.')
dp[i][j]=X[i][j]+Y[i][j]+Z[i][j]
X[i][j]=X[i][j-1]+dp[i][j-1]
Y[i][j]=Y[i-1][j]+dp[i-1][j]
Z[i][j]=Z[i-1][j-1]+dp[i-1][j-1]

(when(i,j) is '#')
dp[i][j]=X[i][j]+Y[i][j]+Z[i][j]
X[i][j]=0
Y[i][j]=0
Z[i][j]=0

Then, the time complexity of this solution is O(HW).

Notes

Don't forget to scanf until S[i][j] is # or . (because \n is read by scanf...)

Code

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
#include<map>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define mod 1000000007
//#define mod 998244353

int H,W;
char S[2000][2000];
int X[2000][2000];//dp[i][j-1]+dp[i][j-2]+...
int Y[2000][2000];
int Z[2000][2000];
int dp[2000][2000];
signed main(){
    scanf("%lld %lld",&H,&W);
    rep(i,H){
        rep(j,W){
            while(S[i][j]!='.' && S[i][j]!='#'){
                scanf("%c",&S[i][j]);
            }
            X[i][j]=0;Y[i][j]=0;Z[i][j]=0;
            dp[i][j]=0;
        }
    }
    //Queen is at (0,0)
    dp[0][0]=1;
    rep(y,H){
        rep(x,W){
            if(y==0&&x==0)continue;
            if(S[y][x]=='.'){
                if(x>0)X[y][x]=dp[y][x-1]+X[y][x-1];
                if(y>0)Y[y][x]=dp[y-1][x]+Y[y-1][x];
                if(x>0&&y>0)Z[y][x]=dp[y-1][x-1]+Z[y-1][x-1];
            }else{
                X[y][x]=0;
                Y[y][x]=0;
                Z[y][x]=0;
            }
            dp[y][x]=X[y][x]+Y[y][x]+Z[y][x];
            X[y][x]%=mod;
            Y[y][x]%=mod;
            Z[y][x]%=mod;
            dp[y][x]%=mod;
        }
    }
    //print the answer
    printf("%lld\n",dp[H-1][W-1]%mod);
    return 0;
}