线上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;
}