P1002 [NOIP 2002 普及组] 过河卒——题解

解题思路

先标记马本身和八个跳跃位置。令 f[i][j] 为到达格子 $(i,j)$ 的路径数。若该格被控制，值为 0；否则从上方和左方转移：f[i][j]=f[i-1][j]+f[i][j-1]。

复杂度分析

时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。

易错点

路径数需要使用 long long。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
long long f[25][25];bool banp[25][25];
int main(){
    int n,m,x,y;cin>>n>>m>>x>>y;
    int dx[9]={0,1,1,2,2,-1,-1,-2,-2};int dy[9]={0,2,-2,1,-1,2,-2,1,-1};
    for(int k=0;k<9;k++){int a=x+dx[k],b=y+dy[k];if(a>=0&&a<=n&&b>=0&&b<=m)banp[a][b]=1;}
    if(!banp[0][0])f[0][0]=1;
    for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){
        if(banp[i][j]){f[i][j]=0;continue;}
        if(i==0&&j==0)continue;
        if(i)f[i][j]+=f[i-1][j];if(j)f[i][j]+=f[i][j-1];
    }
    cout<<f[n][m]<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; long long f[25][25];bool banp[25][25]; int main(){ int n,m,x,y;cin>>n>>m>>x>>y; int dx[9]={0,1,1,2,2,-1,-1,-2,-2};int dy[9]={0,2,-2,1,-1,2,-2,1,-1}; for(int k=0;k<9;k++){int a=x+dx[k],b=y+dy[k];if(a>=0&&a<=n&&b>=0&&b<=m)banp[a][b]=1;} if(!banp[0][0])f[0][0]=1; for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){ if(banp[i][j]){f[i][j]=0;continue;} if(i0&&j0)continue; if(i)f[i][j]+=f[i-1][j];if(j)f[i][j]+=f[i][j-1]; } cout<<f[n][m]<<'\n';return 0; }