NOIP 2002普及组 过河卒详解

本文图片引用自“kcfzyhq”的博客

1.分析

首先我们来看看下面这个图，这个图基本表现了题目的意思：一个卒要从图的左上角A点走到右下角B点，而其中有一点C为马的位置，C与其周边马能走到的P1~P8点共9个点是不能走的，问有多少种从A走到B的方法

我们可以先把这个问题当数学问题来考虑相信许多朋友以前都遇到过类似的数学问题，对于点[i,j]，它的走法数等于它上方点与其左方点走法数之和（因为只能向下或向右走），也就是B[i,j]=B[i-1][j]+b[i][j-1],如下图就是一个例子

但换到有马阻拦的问题中，单纯地这样搜索就行不通了，如下图

这张图所得的答案虽然是正确的，但实际上这样的操作是错误的，图中蓝色的“1”应该改为0，如下图

因为这个位置后面被马头挡住，自然是行不通的，值应为0，在这个例子中这里的值是1还是0对答案没有影响，但大家可以想象，如果在最左边一条边上，一个点上下都是马能走到的位置，值还为1的话，就会影响它右侧点的值（不懂的看下面这个例子）

就像上图，正常情况下红色点所在的一整列初始赋值都是1，但是红色点实际值应该为0，如果值仍赋为1，则会导致蓝色点的值比实际值大1，从而导致整个结果错误。
因此，我们在赋初值时，要专门考虑最上和最左一列的情况，具体方法参见代码

哦，对了，这道题的数据可能很大，注意要开long long，否则会炸

2.AC代码

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

long long B[21][21];
int n,m,a,b;

void init()
{
    for (int i=0;i<=n;i++){ //先把所有点都赋为1，刚刚讲的特殊情况下面再考虑 
        for (int j=0;j<=m;j++){
            B[i][j]=1;
        }
    }
    if(a-2>=0&&b-1>=0)  //把马的位置和所有马能走到的位置都赋为0，注意考虑边界 
        B[a-2][b-1]=0;     
    if(a-2>=0&&b+1<=m)   
        B[a-2][b+1]=0;  
    if(a-1>=0&&b-2>=0)  
        B[a-1][b-2]=0;  
    if(a-1>=0&&b+2<=m)  
        B[a-1][b+2]=0;  
    if(a+1<=m&&b-2>=0)  
        B[a+1][b-2]=0;  
    if(a+2<=n&&b-1>=0)  
        B[a+2][b-1]=0;  
    if(a+1<=n&&b+2<=m)  
        B[a+1][b+2]=0;  
    if(a+1<=n&&b+1<=m)  
        B[a+2][b+1]=0;  
    B[a][b]=0;  
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&a,&b);
    init();
    for (int i=0;i<=n;i++){
        for (int j=0;j<=m;j++){
            if (B[i][j]!=0){
                if (i==0 && j==0){
                    continue;
                }/*这里就是处理所说的特殊情况，相当于如果在最上一行或者最左一行 
                   出现一个马，那么后面的值都赋为0 
                */ 
                else if (i==0){ 
                    B[i][j]=B[i][j-1]; 
                }else if (j==0){
                    B[i][j]=B[i-1][j];
                }else{
                    B[i][j]=B[i-1][j]+B[i][j-1];
                }
            }
        }
    }
    printf("%lld\n",B[n][m]);
}