题目描述

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，$A$ 点 $(0, 0)$、$B$ 点 $(n, m)$，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 $B$ 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

样例 #1

样例输入 #1

6 6 3 3

样例输出 #1

6

提示

对于 $100 \%$ 的数据，$1 \le n, m \le 20$，$0 \le$ 马的坐标 $\le 20$。

【题目来源】

NOIP 2002 普及组第四题

算法1

深度优先遍历（60分）

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio> 
#include<cstring>
using namespace std;

const int N=25;
int arr[N][N];
bool st[N][N];//初始化为false 

int m1,m2,b1,b2;
int dy[9]={2,-2,2,-2,1,-1,1,-1},dx[9]={-1,-1,1,1,-2,-2,2,2};
int cx[2]={1,0},cy[2]={0,1};
int ans=0;//最终答案 

void dfs(int x,int y){
    if(x==b1 && y==b2){
        ans++;
        return;
    } 
    for(int i=0;i<2;i++){
        int x0=x+cx[i],y0=y+cy[i];
        if(x0<0 || y0<0 || x0>b1 || y0>b2 || st[x0][y0]==true)continue;
        if(arr[x0][y0]==-1) continue;
        st[x0][y0]=true;
        dfs(x0,y0);
        st[x0][y0]=false;
    }   
}

int main(){
    memset(arr,0,sizeof arr);
    memset(st,0,sizeof st);
    cin>>b1>>b2>>m1>>m2;
    //加入马的点 包括本身 
    arr[m1][m2]=-1;
    for(int i=0;i<8;i++){
        int xm=m1+dx[i],ym=m2+dy[i];
        if(xm<0 || ym<0 || xm>b1 || ym>b2) continue;
        arr[xm][ym]=-1;
    }
    //搜索
     dfs(0,0);
     cout<<ans;
    return 0;
}

算法2

普通dp 没优化（100分）

C++ 代码

解析链接

https://www.luogu.com.cn/problem/solution/P1002

#include<iostream>
#include<algorithm>
#include<cstdio> 
#include<cstring>
using namespace std;
const int N=25;
long long a[N][N];
bool st[N][N];
int b1,b2,m1,m2;
int dx[9]={0,-1,-1,-2,-2,1,1,2,2},dy[9]={0,2,-2,1,-1,2,-2,1,-1};

/*
1.卒是向下和右走的
2.马的地方不能走 包括本身

*/
int main(){
    cin>>b1>>b2>>m1>>m2;
     memset(a,0,sizeof a);
     b1++;b2++;m1++;m2++;
     a[1][0]=1;
     for(int i=0;i<9;i++){
        int x=m1+dx[i],y=m2+dy[i];
        if(x>=1 && y>=1 && x<=b1 && y<=b2) st[x][y]=true;
     }
     for(int i=1;i<=b1;i++)
        for(int j=1;j<=b2;j++){
            if(st[i][j]==true) a[i][j]=0;
            else a[i][j]=a[i-1][j]+a[i][j-1];
         }
    cout<<a[b1][b2];

//  cout<<endl;
//  for(int i=0;i<=b1;i++){
//      for(int j=0;j<=b2;j++){
//          cout<<a[i][j]<<' ';
//      }
//      cout<<endl;
//  }

    return 0;
}