洛谷 P1002 [NOIP2002 普及组] 过河卒

F0reverK · 2023-11-24 13:35:22 · 题解

思路

普普通通的动态规划（DP）模板题。

选择分两块来讨论问题。

首先处理一下马能移动到的位置，只需要在马所在的坐标和其能移动的八个点位标记即可。通过以下代码实现。

const int dir[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};//移动数组，存下来马每种移动时位置的相对变化
d[cx][cy]=true;//把马本体标记
for(int i=0;i<8;i++){
    int tx=cx+dir[i][0],ty=cy+dir[i][1];//移动
    if(tx>=0&&tx<=n&&ty>=0&&ty<=m)//如果在边界内
        d[tx][ty]=true;//标记
}

然后开始讨论移动的问题，不难发现，点 (i,j) 只能由 (i-1,j) 和 (i,j-1) 移动得到，而到这个点的方案数便是 dp_{i-1,j}+dp_{i,j-1}。

所以得出状态转移方程 dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}，由于到原点的方案数只有 1 种，所以 dp_{0,0}=1，再处理一下边界情况即可。

for(int i=0;i<=n;i++){
    for(int j=0;j<=m;j++){
        if(d[i][j]==false){//如果没被标记
            if(i)//判边界
                dp[i][j]+=dp[i-1][j];//转移
            if(j)//判边界
                dp[i][j]+=dp[i][j-1];//转移
        }
    }
}

AC Code

#include<bits/stdc++.h>
using namespace std;
const int dir[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};
bool d[30][30];
long long dp[30][30],n,m,cx,cy;
int main(){
    cin>>n>>m>>cx>>cy;
    d[cx][cy]=true;
    for(int i=0;i<8;i++){
        int tx=cx+dir[i][0],ty=cy+dir[i][1];
        if(tx>=0&&tx<=n&&ty>=0&&ty<=m) d[tx][ty]=true;
    }
    dp[0][0]=1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(d[i][j]==false){
                if(i) dp[i][j]+=dp[i-1][j];
                if(j) dp[i][j]+=dp[i][j-1];
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}