一本通-1314：【例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

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

vector<vector<long long> > res(21, vector<long long>(21));
vector<vector<int> > grid(25, vector<int>(25));
int m, n;
int x, y;
int direction[8][2] = {{2,1}, {1,2}, {-1,-2}, {-2, -1}, {-2,1}, {-1, 2}, {2, -1}, {1, -2}};

long long cal()
{
    for (int i = 0; i <= m; ++i) {
        if (grid[i][0]) {
            while (i <= m) {
                res[i++][0] = 0;
            }
            break;
        }
        else res[i][0] = 1;
    }

    for (int j = 0; j <= n; ++j) {
        if (grid[0][j]) {
            while (j <= n) {
                res[0][j++] = 0;
            }
            break;
        }
        else res[0][j] = 1;
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (!grid[i][j]) {
                res[i][j] += (grid[i - 1][j] ? 0 : res[i - 1][j]);
                res[i][j] += (grid[i][j - 1] ? 0 : res[i][j - 1]);
            }
        }
    }

    return res[m][n];
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> m >> n >> x >> y;
    grid[x][y] = 1;
    for (int i = 0; i < 8; ++i) {
        int row = x + direction[i][0];
        int col  = y + direction[i][1];
        if (0 <= row && row <= m && 0 <= col && col <= n) {
            grid[row][col] = 1;
        }
    }

    cout << cal() << endl;

    return 0;
}

这道题思路不难，细节颇多。比如在设置障碍点为1的时候不能漏掉马初始的位置（自己第一遍就漏掉了），另外这道题没提到取模，则在20规模的情况下很可能造成整型溢出，所以需要使用long long的类型。

另外就是初始化的问题，第0行和第0列需要初始化，则只要有一个点能被马达到，则这一行或这一列后面的结果（res）都是0.