背景

依稀记得Mod(gf24153)开始再洛谷开始做题的那个下午，它(即Mod)就点进了这道过河卒(即bcoi·过河卒)。它是一道动态规划的题目，可惜我们还在学DFS和BFS。显然用DFS是要超时的

---

题目

【题目描述】

棋盘上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

---

题解

DFS解法

先尝试用深搜解决这道题。标记🐎的位置及🐎可以走到的格子，然后从(0,0)开始深搜，如果走到(n,m)就ans++。

#include <iostream>//头文件
using namespace std;//命名空间
int n, m, mx, my, a[25][25], ans;//先定义了再说
bool vis[25][25];//先定义了再说
int dx[] = {0, 0, 1};//由于只有两个方向
int dy[] = {0, 1, 0};//先定义了再说
int mdx[] = {0, -2, -1, 1, 2,  2,  1, -1, -2};//如41行
int mdy[] = {0,  1,  2, 2, 1, -1, -2, -2, -1};//先定义了再说
bool check(int x, int y)//检查新的点能不能走
{//简单的check函数
    if (x < 1 || x > n || y < 1 || y > m)return 0;//出界就false
    if (a[x][y])return 0;//不能走就false
    if (vis[x][y])return 0;//走过就false
    return 1;//只好true了
}
void dfs(int x, int y)//用来搜索路径总数
{
    if (x == n && y == m)//到达终点
    {
        ans++;//路径数加一
        return ;//到终点就不要搜了
    }
    for (int i = 1; i <= 2; i++)//二方向
    {//很经典的路径代码
        int nx = x + dx[i];//先定义了再说
        int ny = y + dy[i];//先定义了再说
        if (check(nx, ny))//检查
        {
            vis[nx][ny] = 1;//标记走过了
            dfs(nx, ny);//递归
            vis[nx][ny] = 0;//回溯
        }
    }
}
int main()//简单的主函数
{
    cin >> n >> m >> mx >> my;//先输入了再说
    n++, m++, mx++, my++;//加加可能更符合my brain
    for (int i = 0; i <= 8; i++)//从0开始只因有马的不能走
    {//这里的mdx和mdy也是直接复制骑士牛
        a[mx + mdx[i]][my + mdy[i]] = 1;//直接标记
    }
    a[1][1] = 1;//起点不能走
    dfs(1, 1);//不管了，直接搜
    cout << ans;//答案
    return 0;//华丽结束。。。
}

注释打的好辛苦！

好吧，打了这么久（的注释）竟然 60 Time Exceeded ！！！

动态规划解法

既然深搜解不了，那只好用动态规划了。定dp[1...n][1...m]数组表示道第(i,j)有多少路径。从(0,0)开始（dp[0][0]等于1，即有一条路），每格的路径数就是上方的路径数（从上方来）加上左方的路径数（从左方来）。最后输出dp[n][m]。得到状态转移方程：

$$\begin{align} dp[i][j] &= \begin{cases} 1 & i=j=1 \\ dp[i-1][j] + dp[i][j-1] & i>1,j>1 \end{cases} \end{align} $$

代码：

#include <iostream>
using namespace std;
int n, m, mx, my, a[25][25], dp[25][25];
int mdx[] = {0, -2, -1, 1, 2,  2,  1, -1, -2};
int mdy[] = {0,  1,  2, 2, 1, -1, -2, -2, -1};
int main()
{
    cin >> n >> m >> mx >> my;
    n++, m++, mx++, my++;
    for (int i = 0; i <= 8; i++)
    {
        a[mx + mdx[i]][my + mdy[i]] = 1;
    }//以上与DFS解法相同
    dp[1][1] = 1;//初始状态
    for (int i = 1; i <= n; i++)
    {
    	for (int j = 1; j <= m; j++)
    	{
    		if (a[i][j]) continue;
            if (i > 1) dp[i][j] += dp[i-1][j];
            if (j > 1) dp[i][j] += dp[i][j-1];//状态转移方程
		}
	}
    cout << dp[n][m];//输出
    return 0;//。。。
}

可是提交了怎么是 60 Wrong Answer ？仔细一看它的解释：

Read 642789722, expect 56477364570.
Read -2091005866, expect 2203961430.

既然得到负数，而且数字那么大，那想必是数据类型的问题了。加上#define int long long，果然AC