P1002 [NOIP2002 普及组] 过河卒题解

Vct14 · 2022-11-27 21:23:07 · 个人记录

本题思路：

由于卒只能向下或向右，所以可以使用标数法。
在标数法时，需从上到下，从左到右标。
如果 a_{i,j} 为马或马的控制点，即无法到达此点， cnt_{i,j}=0 。
因为起点到起点只有 1 种路线，所以 cnt_{0,0}=1 。

怎样标数：

当 i \geq 1 且 j \geq 1 时，cnt_{i,j}=cnt_{i-1,j}+cnt_{i,j-1} 。
当 i = 0 且 j \geq 1 时，cnt_{i,j}=cnt_{i,j-1} 。
当 i \geq 1 且 j = 0 时，cnt_{i,j}=cnt_{i-1,j} 。

样例解释：

（起点 Begin ，马 Horse ，终点 End）

	0	1	2	3	4	5	6
0	B	1	1	1	1	1	1
1	1	2	\color{red}\text{x}	1	\color{red}\text{x}	1	2
2	1	\color{red}\text{x}	0	1	1	\color{red}\text{x}	2
3	1	1	1	H	1	1	3
4	1	\color{red}\text{x}	1	1	3	\color{red}\text{x}	3
5	1	1	\color{red}\text{x}	1	\color{red}\text{x}	0	3
6	1	2	2	3	3	3	E

答案：3+3=6 。

#include<bits/stdc++.h>
using namespace std;

bool a[21][21];//标注能否走，true 就无法走
long long cnt[21][21]; //标数
int n,m,x,y;

void Can_Not_Go(){//判断是否是马或马的控制点
    a[x][y]=true;//马
   //马走日
    if(x+2<=n && y+1<=m) a[x+2][y+1]=true;
    if(x+1<=n && y+2<=m) a[x+1][y+2]=true;
    if(x-1>=0 && y+2<=m) a[x-1][y+2]=true;
    if(x-2>=0 && y+1<=m) a[x-2][y+1]=true;
    if(x-2>=0 && y-1>=0) a[x-2][y-1]=true;
    if(x-1>=0 && y-2>=0) a[x-1][y-2]=true;
    if(x+1<=n && y-2>=0) a[x+1][y-2]=true;
    if(x+2<=n && y-1>=0) a[x+2][y-1]=true;
   //马的控制点
}

void init(){//初始化
    Can_Not_Go();
    cnt[0][0]=1;//起点有一种路线
}

int main(){
    cin>>n>>m>>x>>y;//输入
   init();//初始化
    for(int i=0; i<=n; i++){//标数
        for(int j=0; j<=m; j++){
            if(i==0 && j==0) continue;//起点跳过
            if(a[i][j]){//不能走
            cnt[i][j]=0;
            continue;
         }
            if(i==0) cnt[i][j]=cnt[0][j-1];//i=0的情况
            else if(j==0) cnt[i][j]=cnt[i-1][0];//j=0的情况
            else cnt[i][j]=cnt[i][j-1]+cnt[i-1][j];//其他正常情况
        }
    }
    cout<<cnt[n][m];//输出终点的数
    return 0;
}

P1002 [NOIP2002 普及组] 过河卒 题解

P1002 [NOIP2002 普及组] 过河卒题解