本文详解如何将网格中的船移动问题建模为图搜索问题，使用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 <blockquote>
<p>⚠️ <strong>重要提醒</strong>：原始 BoatMovements.dfs_search 实现中仍按标准四邻接递归（±1,±1），这会导致逻辑矛盾——它试图搜索任意路径，但题目明确要求“<strong>在一步内</strong>从起点到达终点”。重读题干：“returns a boolean indicating whether a boat can travel between the two points <strong>in one step</strong>”。<br>
✅ 正确理解：这不是多步路径规划，而是<strong>单步可达性判断</strong>！无需DFS/BFS——只需直接验证目标位置是否满足位移规则且路径上所有格子均为水。 </p>
<p><strong>终极简化解法（推荐）</strong>： </p>
<pre class="brush:php;toolbar:false;">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
该解法时间复杂度 O(1)，鲁棒性强，完全契合题意。图算法思想在此体现为：将“单步移动”抽象为带约束的边存在性判断，而非盲目遍历。
