过河卒 题解

· · 题解

2022/3/1 备注：博主已经退役，将不再处理本题解评论区中的问题。

一个很经典的 DP 水题。

思路其实非常简单啊，就是小学奥数的标数法，相信各位应该都是非常熟悉的。

那递推公式就是 dp[i][j]=dp[i-1][j]+dp[i][j-1] 了。

注意讨论马的控制点不能进入就好了。还有注意开 long long。

#include<bits/stdc++.h>
using namespace std;
bool vis[25][25];
long long step[25][25];//就是 dp 数组
int main()
{
    step[1][1]=1;
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    n++;
    m++;
    x++;
    y++;
    vis[x][y]=1;
    vis[x-2][y-1]=1;
    vis[x-2][y+1]=1;
    vis[x+2][y-1]=1;
    vis[x+2][y+1]=1;
    vis[x-1][y+2]=1;
    vis[x-1][y-2]=1;
    vis[x+1][y+2]=1;
    vis[x+1][y-2]=1;//标记一下马的控制点
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) if((i!=1||j!=1)&&!vis[i][j]) step[i][j]=step[i-1][j]+step[i][j-1];//不能走进马的控制点
    cout<<step[n][m];
    return 0;
}