【openjudge】【递推】例3.6 过河卒(Noip2002)

【题目描述】

棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。

【输入】

给出n、m和C点的坐标。

【输出】

从A点能够到达B点的路径的条数。

【输入样例】
8 6 0 4
【输出样例】
1617

【算法分析：】

20*20的格子用dfs会超时，标算应该是递推.

f[i][j]表示从点(0, 0)到达点(i, j)的路径条数，vis[i][j]为1表示点(i, j)是马的控制点

递推式由分类加法很容易得到：

　　f[i][j] = f[i - 1][j] + f[i][j - 1];

i, j >= 1 、i <= n 、j <= m、vis[i][j] = 0

比较需要注意的是初始化：

不能只是把边界点赋成1，如果边界上有马的控制点就GG了..

如果这个点是马的控制点，其后的所有点都无法到达

有一种比较方便的初始化写法：

f[0][0] = vis[0][0] ^ 1;
for(int i = 1; i <= m; i++) f[0][i] = f[0][i - 1] ^ vis[0][i];
for(int i = 1; i <= n; i++) f[i][0] = f[i - 1][0] ^ vis[i][0];

【代码：】

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

const int dx[8] = {2, 2, 1, 1, -2, -2, -1, -1};
const int dy[8] = {1, -1, 2, -2, 1, -1, 2, -2};

//注意开long long
long long n, m, xc, yc;
long long ans, f[21][21];
bool vis[21][21];

int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &xc, &yc);
    vis[xc][yc] = 1;
    for(int i = 0; i < 8; i++) {
        int xx = xc + dx[i], yy = yc + dy[i];
        if(xx <= n && yy <= m && xx >= 0 && yy >= 0)
            vis[xc + dx[i]][yc + dy[i]] = 1;
    }
    f[0][0] = vis[0][0] ^ 1;
    for(int i = 1; i <= m; i++) f[0][i] = f[0][i - 1] ^ vis[0][i];
    for(int i = 1; i <= n; i++) f[i][0] = f[i - 1][0] ^ vis[i][0];
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(!vis[i][j])
                f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    printf("%lld
", f[n][m]);
}