当前位置：首页 > news >正文

用C语言解决‘马拦过河卒’：一个动态规划的经典入门案例（附完整代码）

news 2026/6/4 13:12:00

用C语言解决‘马拦过河卒’：动态规划思想的实战演练

棋盘上一个小卒要从A点走到B点，只能向右或向下移动。但棋盘上还有一匹敌方的马，它会阻挡小卒前进的路线。这个看似简单的棋盘问题，实际上蕴含着动态规划的核心思想。对于刚接触算法的新手来说，这是一个绝佳的入门案例——它不需要复杂的数学推导，却能清晰展示动态规划解决问题的完整过程。

1. 问题理解与建模

"马拦过河卒"问题描述了一个经典的路径计数场景：在棋盘坐标系中，卒子从原点(0,0)出发，每次只能向右或向下移动一格，最终到达目标点(n,m)。但棋盘上存在一个敌方马及其控制点（马走"日"字能到达的8个位置），这些点构成卒子无法通过的障碍。

关键问题要素：

棋盘坐标系：原点在左上角，x轴向右，y轴向下
卒子移动规则：仅能→或↓
障碍点：马的位置及其8个控制点
求解目标：计算从(0,0)到(n,m)的所有可行路径数

这个问题的动态规划解法需要建立两个核心概念：

状态表示：用二维数组f[i][j]表示从起点到点(i,j)的路径数
状态转移：f[i][j] = f[i-1][j] + f[i][j-1]（来自上方或左方的路径和）

2. 动态规划框架搭建

2.1 数据结构初始化

首先需要初始化两个关键数组：

int f[20][20]; // 存储路径数 int g[20][20]; // 标记障碍点（1表示不可达）

初始化过程包括：

将所有f[i][j]初始化为0
将所有g[i][j]初始化为0
标记马的位置及其控制点为1（障碍）

// 初始化数组 for(int i=0; i<=n; i++){ for(int j=0; j<=m; j++){ f[i][j] = 0; g[i][j] = 0; } } // 标记马的控制点 g[x][y] = 1; // 马的位置 g[x-1][y+2] = 1; // 马的8个控制点 g[x-1][y-2] = 1; g[x-2][y+1] = 1; g[x-2][y-1] = 1; g[x+1][y+2] = 1; g[x+1][y-2] = 1; g[x+2][y+1] = 1; g[x+2][y-1] = 1;

2.2 边界条件处理

动态规划问题的边界处理至关重要。对于棋盘的第一行和第一列：

第一行：只能从左边过来（如果左边可达）
第一列：只能从上方过来（如果上方可达）

// 处理第一行 for(int j=0; j<=m; j++){ if(g[0][j] == 0){ f[0][j] = 1; // 可达则路径数为1 } else { // 遇到障碍，后面所有点都不可达 for(; j<=m; j++) f[0][j] = 0; break; } } // 处理第一列 for(int i=0; i<=n; i++){ if(g[i][0] == 0){ f[i][0] = 1; // 可达则路径数为1 } else { // 遇到障碍，后面所有点都不可达 for(; i<=n; i++) f[i][0] = 0; break; } }

注意：边界处理时要特别注意障碍点的连锁效应——一旦某点不可达，其后的所有点也都不可达。

3. 核心动态规划实现

3.1 状态转移方程

动态规划的核心在于状态转移方程的设计。对于棋盘内部点(i,j)（i>0且j>0），路径数计算遵循：

如果(i,j)不是障碍点： f[i][j] = f[i-1][j] + f[i][j-1] 否则： f[i][j] = 0

这一方程直观反映了卒子的移动规则：到达(i,j)的路径只能来自上方(i-1,j)或左方(i,j-1)。

3.2 双重循环实现

用双重循环填充整个f数组：

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

这个看似简单的循环，实际上完成了动态规划最关键的步骤——自底向上构建解空间。

3.3 结果输出

最终结果存储在f[n][m]中：

printf("%d\n", f[n][m]);

4. 完整代码实现与优化

4.1 完整代码整合

将上述各部分整合，得到完整解决方案：

#include <stdio.h> int main() { int n, m, x, y; scanf("%d %d %d %d", &n, &m, &x, &y); int f[20][20] = {0}; // 路径数数组 int g[20][20] = {0}; // 障碍标记数组 // 标记马的控制点 g[x][y] = 1; int dx[] = {-1, -1, -2, -2, 1, 1, 2, 2}; int dy[] = {2, -2, 1, -1, 2, -2, 1, -1}; for(int k=0; k<8; k++){ int nx = x + dx[k]; int ny = y + dy[k]; if(nx>=0 && nx<=n && ny>=0 && ny<=m){ g[nx][ny] = 1; } } // 处理第一行 for(int j=0; j<=m; j++){ if(g[0][j] == 0){ f[0][j] = 1; } else { for(; j<=m; j++) f[0][j] = 0; break; } } // 处理第一列 for(int i=0; i<=n; i++){ if(g[i][0] == 0){ f[i][0] = 1; } else { for(; i<=n; i++) f[i][0] = 0; break; } } // 动态规划填充 for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(g[i][j] == 0){ f[i][j] = f[i-1][j] + f[i][j-1]; } } } printf("%d\n", f[n][m]); return 0; }

4.2 代码优化技巧

马控制点的标记优化：使用方向数组简化代码：

int dx[] = {-1, -1, -2, -2, 1, 1, 2, 2}; int dy[] = {2, -2, 1, -1, 2, -2, 1, -1}; for(int k=0; k<8; k++){ int nx = x + dx[k]; int ny = y + dy[k]; if(nx>=0 && nx<=n && ny>=0 && ny<=m){ g[nx][ny] = 1; } }

边界条件检查优化：可以提前检查起点或终点是否为障碍点：
```
if(g[0][0] == 1 || g[n][m] == 1){ printf("0\n"); return 0; }
```
数组大小调整：根据题目约束（n,m≤15），数组大小可以适当减小：
```
int f[16][16] = {0}; int g[16][16] = {0};
```