引言
“过河卒”是中国象棋术语，指卒子过河后只能前进或横走，不能后退。在算法竞赛中，过河卒问题被抽象为：在一个 m×n 的棋盘上，棋子从左上角出发，每次只能向右或向下移动一格，求到达右下角的路径总数。若棋盘上存在障碍物，则需绕过障碍。本文用Java实现过河卒问题的动态规划求解，并扩展至带障碍的网格路径计数。
问题建模
设棋盘为 m 行 n 列的二维网格。棋子从 (0,0) 出发，目标为 (m-1, n-1)。每次只能向 右（列+1）或向 下（行+1）移动。若某些格子被标记为障碍，则不可经过。
这是一个典型的组合计数问题。无障碍时，路径总数为组合数 C(m+n-2, m-1)。有障碍时，需使用动态规划逐格计算。
动态规划状态设计
定义 dp[i][j] 表示从起点到达格子 (i,j) 的路径数量。状态转移方程为：
if grid[i][j] 是障碍:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界条件：dp[0][0] = 1（起点），第一行和第一列的格子只能从左侧或上方到达，若前方有障碍则后续格子均为0。
Java实现
import java.util.*;
/**
* 过河卒：动态规划路径计数与障碍规避
*/
public class RiverCrossingPawn {
static final int MOD = 1_000_000_007; // 大数取模，防止溢出
/**
* 基础版：无障碍网格的路径计数
* 使用一维DP优化空间
*/
public static long countPaths(int m, int n) {
// dp[j] 表示当前行到达第j列的路径数
long[] dp = new long[n];
dp[0] = 1; // 起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue; // 跳过起点
long fromTop = (i > 0) ? dp[j] : 0;
long fromLeft = (j > 0) ? dp[j - 1] : 0;
dp[j] = (fromTop + fromLeft) % MOD;
}
}
return dp[n - 1];
}
/**
* 扩展版：带障碍网格的路径计数
* @param obstacles 障碍物坐标列表，每个元素为 int[]{row, col}
*/
public static long countPathsWithObstacles(int m, int n, List<int[]> obstacles) {
// 标记障碍格
boolean[][] blocked = new boolean[m][n];
for (int[] obs : obstacles) {
blocked[obs[0]][obs[1]] = true;
}
// 若起点或终点被堵，直接返回0
if (blocked[0][0] || blocked[m - 1][n - 1]) return 0;
long[][] dp = new long[m][n];
dp[0][0] = 1;
// 初始化第一行：只能从左边来，遇到障碍则后续全为0
for (int j = 1; j < n; j++) {
if (blocked[0][j]) {
dp[0][j] = 0;
} else {
dp[0][j] = dp[0][j - 1];
}
}
// 初始化第一列：只能从上边来
for (int i = 1; i < m; i++) {
if (blocked[i][0]) {
dp[i][0] = 0;
} else {
dp[i][0] = dp[i - 1][0];
}
}
// 逐行逐列填充DP表
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (blocked[i][j]) {
dp[i][j] = 0;
} else {
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
}
}
}
return dp[m - 1][n - 1];
}
/**
* 空间优化版：带障碍网格仅用O(n)空间
*/
public static long countPathsWithObstaclesOptimized(int m, int n, List<int[]> obstacles) {
boolean[][] blocked = new boolean[m][n];
for (int[] obs : obstacles) {
blocked[obs[0]][obs[1]] = true;
}
if (blocked[0][0] || blocked[m - 1][n - 1]) return 0;
long[] dp = new long[n];
dp[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
if (blocked[i][j]) {
dp[j] = 0;
} else {
long fromTop = dp[j]; // 上一行同列的值（尚未被覆盖）
long fromLeft = (j > 0) ? dp[j - 1] : 0;
dp[j] = (fromTop + fromLeft) % MOD;
}
}
}
return dp[n - 1];
}
/**
* 进一步扩展：带障碍的最短路径（BFS）与最长路径（DAG DP）
* 此处展示最短路径版本，用于对比理解
*/
public static int shortestPathWithObstacles(int m, int n, List<int[]> obstacles) {
boolean[][] blocked = new boolean[m][n];
for (int[] obs : obstacles) blocked[obs[0]][obs[1]] = true;
if (blocked[0][0] || blocked[m - 1][n - 1]) return -1;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, -1);
dist[0][0] = 0;
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0});
int[] dr = {0, 1}; // 右、下
int[] dc = {1, 0};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int r = cur[0], c = cur[1];
if (r == m - 1 && c == n - 1) return dist[r][c];
for (int d = 0; d < 2; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < m && nc < n && !blocked[nr][nc] && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
queue.offer(new int[]{nr, nc});
}
}
}
return -1; // 无法到达
}
/**
* 打印带障碍的棋盘可视化
*/
static void printGrid(int m, int n, List<int[]> obstacles, long[][] dp) {
boolean[][] blocked = new boolean[m][n];
for (int[] obs : obstacles) blocked[obs[0]][obs[1]] = true;
System.out.println("棋盘与路径数（X表示障碍）：");
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (blocked[i][j]) {
System.out.print(" X ");
} else {
System.out.printf("%5d ", dp[i][j]);
}
}
System.out.println();
}
}
public static void main(String[] args) {
// 示例1：5x5 无障碍
System.out.println("=== 5x5 无障碍 ===");
System.out.println("路径总数：" + countPaths(5, 5));
// 理论值 C(8,4) = 70
// 示例2：5x5 带障碍
System.out.println("\n=== 5x5 带障碍 ===");
List<int[]> obs = Arrays.asList(
new int[]{1, 1},
new int[]{2, 3},
new int[]{3, 1}
);
long ways = countPathsWithObstacles(5, 5, obs);
System.out.println("路径总数（带障碍）：" + ways);
// 打印DP表
boolean[][] blocked = new boolean[5][5];
for (int[] o : obs) blocked[o[0]][o[1]] = true;
long[][] dp = new long[5][5];
dp[0][0] = 1;
for (int j = 1; j < 5; j++) dp[0][j] = blocked[0][j] ? 0 : dp[0][j-1];
for (int i = 1; i < 5; i++) dp[i][0] = blocked[i][0] ? 0 : dp[i-1][0];
for (int i = 1; i < 5; i++)
for (int j = 1; j < 5; j++)
dp[i][j] = blocked[i][j] ? 0 : (dp[i-1][j] + dp[i][j-1]) % MOD;
printGrid(5, 5, obs, dp);
// 示例3：最短路径
System.out.println("\n最短路径长度（带障碍）：" + shortestPathWithObstacles(5, 5, obs));
}
}
复杂度分析
- 时间复杂度：
O(m × n)，每个格子仅计算一次。 - 空间复杂度：
- 二维DP版：
O(m × n)； - 一维优化版：
O(n)，仅用一维数组滚动更新。
对于极大棋盘（如 10^5 × 10^5），一维优化是必要手段。若结果需要对大质数取模，所有加法操作后及时取模即可。
总结
过河卒问题是理解二维动态规划的绝佳入门案例。从基础路径计数到障碍规避，再到空间优化与BFS最短路径扩展，本文逐步构建了完整的求解体系。核心思想是：将几何路径问题转化为状态递推，利用最优子结构避免重复计算。读者可进一步尝试”带权网格的最小/最大路径和”等进阶变体。
