Author: loop3r
Date: 20260224
tag: 递推
link: https://www.luogu.com.cn/problem/P1002

问题描述

link

分析

首先将坐标全部加 $1$，方便后续处理。

考虑马不存在时，从左上角 $(1,1)$ 到右下角 $(n,m)$ 的路径数。

设 $f[i][j]$ 表示从 $(1,1)$到$(i,j)$ 的路径数，则有：

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

即卒只能笔直往右或者笔直往下走一步从上一个位置到达 $(i,j)$。

初始条件：$f[1][j]=1,j\in [1,m]$；$f[i][1]=1,i\in [1,n]$。

为了方便处理，我们可以令 $f[0][1]=1$ 或 $f[1][0]=1$，这样就不需要单独处理边界条件了。

最后答案就是 $f[n][m]$。

考虑马存在时，可以标记马及马拦截的位置，当递推到标记位置时，记录路径数为 $0$即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
long long f[25][25];
bool st[25][25];
int n, m, x, y;

int main() {
	cin >> n >> m >> x >> y;
	n++, m++, x++, y++;

	st[x][y] = true;
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
		st[nx][ny] = true;
	}

	f[0][1] = 1; // f[1][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (st[i][j]) continue;
			f[i][j] = f[i - 1][j] + f[i][j - 1];
		}
	}

	cout << f[n][m] << endl;

	return 0;
}