♐ CSP_J 组真题
2002年
4. 过河卒

线上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动态规划

方法:从起点开始逐步计算到达每个位置的路径数。对于每个位置,它的路径数 等于 左边和上边位置的路径数之和(如果存在的话),同时要考虑到不能走被禁止的位置。
状态转移方程dp[i][j]=dp[i1][j]+dp[i][j1]dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
状态初始化:

第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;
}