线上OJ 地址：
一本通：1921：【02NOIP普及组】过河卒 (opens in a new tab)
AcWing：5493. 过河卒 (opens in a new tab)
洛谷：P1002 [NOIP2002 普及组] 过河卒 (opens in a new tab)
核心思想：
对于此类棋盘问题，一般可以考虑 dp动态规划、dfs深搜 和 bfs广搜。
解法一：dp动态规划
方法：从起点开始逐步计算到达每个位置的路径数。对于每个位置，它的路径数 等于 左边和上边位置的路径数之和（如果存在的话），同时要考虑到不能走被禁止的位置。
状态转移方程：
状态初始化：
第0行只能从左边转移过来；
第0列只能从上面转移过来；
dp[0][0]为1，表示自己到自己有1种方法。
注意：计算马的屏蔽坐标时不要遗漏马本身
特别注意：虽然只有20个格子，但本题的结果数据很大。开 int 只能60分，需要 开 long long 方能100分
题解代码：
dp动态规划
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 25;
ll dp[N][N]; // 不开 long long 见祖宗
bool hasBlock[N][N]; // hasBlock[i][j] 为true,表示该位置被马控制了，不能走
// 计算不能走的区域(本题为马的控制区域)
void cmp(int x, int y, int n, int m)
{
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
hasBlock[x][y] = true; // 马本身的坐标屏蔽
for (int i = 0; i < 8; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx <= n && ny >= 0 && ny <= m)
hasBlock[nx][ny] = true; // 马控制的8个区域不能走
}
}
int main()
{
int n, m, x, y;
scanf("%d %d %d %d", &n, &m, &x, &y);
cmp(x, y, n, m); // 先标记所有不能走的区域
memset(dp, 0, sizeof(dp));
dp[0][0] = 1; // 初始化第一个
for(int j = 1; j <= m; j++)
if(!hasBlock[0][j]) dp[0][j] = dp[0][j-1]; // 初始化第一行
for(int i = 1; i <= n; i++)
if(!hasBlock[i][0]) dp[i][0] = dp[i-1][0]; // 初始化第一列
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!hasBlock[i][j])
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 状态转移方程
cout << dp[n][m] << endl;
return 0;
}