本文详解如何将网格中的船移动问题建模为图搜索问题，使用dfs判断在限定步长规则（横向1格、纵向2格）下是否可达，并修正边界检查与移动约束逻辑。
本文详解如何将网格中的船移动问题建模为图搜索问题，使用dfs判断在限定步长规则（横向1格、纵向2格）下是否可达，并修正边界检查与移动约束逻辑。
在游戏网格中模拟船的移动，本质上是一个受限路径可达性问题：船只能在水（True）格子上行驶，且每一步的位移严格受限——仅允许向左/右移动1格，或向上/向下移动2格（注意：不是“最多2格”，而是“恰好2格”）。这并非标准的四邻接图遍历，而是一个自定义边规则的隐式图：每个水单元是图的节点，节点间存在有向边当且仅当满足位移约束且目标格也为水。
因此，解决方案需分两层设计：
- 合法性预检：快速排除明显不可达情况（越界、起点/终点非水、位移不满足 |Δr|=2 且 Δc=0 或 |Δc|=1 且 Δr=0）；
- 图搜索验证：使用深度优先搜索（DFS）或广度优先搜索（BFS）探索所有符合规则的路径。
关键修正点在于原实现中对移动规则的理解偏差：
❌ 错误：abs(to_row - from_row) > 2（允许0、1、2格移动）
✅ 正确：必须精确匹配移动模式——即 (Δr, Δc) 只能是 (±2, 0)、(0, ±1) 四种之一。因此预检逻辑应为：
# 正确的移动约束检查
row_diff = abs(to_row - from_row)
col_diff = abs(to_column - from_column)
if not ((row_diff == 2 and col_diff == 0) or (row_diff == 0 and col_diff == 1)):
return False同时，边界检查需严谨：列数上限应为 len(game_matrix[0]) - 1，而非 len(game_matrix) - 1（原代码中 to_column > len(game_matrix) - 1 是典型错误）。
完整可运行的 can_travel_to 实现如下：
def can_travel_to(game_matrix, from_row, from_column, to_row, to_column):
# 1. 边界检查：确保所有坐标在有效范围内
if (not (0 <= from_row < len(game_matrix) and
0 <= from_column < len(game_matrix[0]) and
0 <= to_row < len(game_matrix) and
0 <= to_column < len(game_matrix[0]))):
return False
# 2. 移动规则检查：仅允许 (±2,0) 或 (0,±1)
row_diff = abs(to_row - from_row)
col_diff = abs(to_column - from_column)
if not ((row_diff == 2 and col_diff == 0) or (row_diff == 0 and col_diff == 1)):
return False
# 3. 水域检查：起点和终点必须为水（True）
if not game_matrix[from_row][from_column] or not game_matrix[to_row][to_column]:
return False
# 4. DFS 搜索路径（复用原 BoatMovements 类，但需确保其 valid_move 支持新规则）
boat = BoatMovements(game_matrix, to_row, to_column)
return boat.dfs_search(from_row, from_column)
# 注意：原 BoatMovements.valid_move 方法需同步更新，禁止任意四邻接，
# 而应在 dfs_search 中显式生成合法下一步（推荐重构为 BFS 更清晰）⚠️ 重要提醒：原始 BoatMovements.dfs_search 实现中仍按标准四邻接递归（±1,±1），这会导致逻辑矛盾——它试图搜索任意路径，但题目明确要求“在一步内从起点到达终点”。重读题干：“returns a boolean indicating whether a boat can travel between the two points in one step”。
✅ 正确理解：这不是多步路径规划，而是单步可达性判断！无需DFS/BFS——只需直接验证目标位置是否满足位移规则且路径上所有格子均为水。终极简化解法（推荐）：
def can_travel_to(game_matrix, from_row, from_column, to_row, to_column): h, w = len(game_matrix), len(game_matrix[0]) # 边界与水域检查 if not (0 <= from_row < h and 0 <= from_column < w and 0 <= to_row < h and 0 <= to_column < w and game_matrix[from_row][from_column] and game_matrix[to_row][to_column]): return False # 精确移动规则 dr, dc = abs(to_row - from_row), abs(to_column - from_column) if not ((dr == 2 and dc == 0) or (dr == 0 and dc == 1)): return False # 验证路径中间格子（纵向2格需检查中间行；横向1格无中间格） if dr == 2: mid_row = (from_row + to_row) // 2 if not game_matrix[mid_row][from_column]: # 中间格必须为水 return False return True
该解法时间复杂度 O(1)，鲁棒性强，完全契合题意。图算法思想在此体现为：将“单步移动”抽象为带约束的边存在性判断，而非盲目遍历。
