题解 P1002 【过河卒】

· · 题解

这是我在洛谷的第一篇题解，希望大家多多支持哦~

（此题的思路来源于《信息学奥赛一本通》中第二部分 基础算法的递推算法）

大家看到这题一般会用搜索来做，也许调试时全过，但运行时当n、m=15时就会超时

其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边或上面过来（以下称为左点和上点）

所以，根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的路径数目

障碍点（马的控制点）也完全适用，只要将到达该店的路径数目设置为0即可

递推关系式如下：

a[i][j]=a[i-1][j]+a[i][j-1]

代码如下：

#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#define MAXN 110
bool b[MAXN][MAXN];
long long a[MAXN][MAXN];
int dx[8]={2,1,-1,-2,-2,-1,1,2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
int n,m,x,y;
using namespace std;
int main(){
    cin>>n>>m>>x>>y;
    memset(b,0,sizeof(b));
    b[x][y]=1;
    for(int i=0;i<=7;i++){
         if(x+dx[i]>=0&&x+dx[i]<=n&&y+dy[i]>=0&&y+dy[i]<=m){
            b[x+dx[i]][y+dy[i]]=1;
         }
    }
    int k=0;
    while(!b[k][0]&&k<=n){
        a[k++][0]=1;
    }
    int l=0;
    while(!b[0][l]&&l<=m){
        a[0][l++]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[i][j]){
                a[i][j]=0;  //g[i][j]=1
            }
            else{
                a[i][j]=a[i-1][j]+a[i][j-1];  //i>0且j>0且g[i][j]=0
            }
        }
    }
    cout<<a[n][m];
    return 0;
}

希望大家多多提出宝贵的意见！

【既然你耐心看完了这篇题解，何不如点个赞再走呢？Thanks♪(･ω･)ﾉ】