[ABC183E] Queen on Grid 题解

· · 题解

题意：

其实题面里已经说的比较清楚了，不过需要注意，在这一题里，可以向一个方向走无数步，直到撞到地图边界或者不能走的墙上。

思路：

由于可以连续走无数步，所以这个点的方案数就等于走过来的三个方向的“线”上的点的方案数之和，以往前推遇到的第一个不可走的点为这个方向上的“线”的起点，以当前点为“线”的结尾。我们发现，可以利用前缀和来计算这条线的结果，我们只需要把每个点对应的方向计算出前缀和，就不难得到每个点的方案数。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[2040][2040],f[2040][2040][3];//long long 保险
bool b[2040][2040];
int main(){
    cin>>n>>m;
    a[1][1]=1;//初始化
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='.') b[i][j]=true;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!b[i][j]) continue;//如果不能走就跳过
            a[i][j]+=f[i-1][j][0]+f[i][j-1][1]+f[i-1][j-1][2];
            //上一格同方向总方案数+这一格方案数=前缀和
            f[i][j][0]=f[i-1][j][0]+a[i][j];
            f[i][j][1]=f[i][j-1][1]+a[i][j];
            f[i][j][2]=f[i-1][j-1][2]+a[i][j];
            //取模
            a[i][j]%=1000000007;
            f[i][j][2]%=1000000007;
            f[i][j][1]%=1000000007;
            f[i][j][0]%=1000000007;
        }
    }
    cout<<a[n][m];//输出结果
    return 0;
}

感觉可以评绿了……