如何用图算法解决船的移动问题

大家好，今天本人给大家带来文章《如何用图算法解决船的移动问题 》，文中内容主要涉及到，如果你对文章方面的知识点感兴趣，那就请各位朋友继续看下去吧~希望能真正帮到你们，谢谢！

本文详解如何将网格中的船移动问题建模为图搜索问题，使用DFS判断在限定步长规则（横向1格、纵向2格）下是否可达，并修正边界检查与移动约束逻辑。

本文详解如何将网格中的船移动问题建模为图搜索问题，使用DFS判断在限定步长规则（横向1格、纵向2格）下是否可达，并修正边界检查与移动约束逻辑。

在游戏网格中模拟船的移动，本质上是一个受限路径可达性问题：船只能在水（True）格子上行驶，且每一步的位移严格受限——仅允许向左/右移动1格，或向上/向下移动2格（注意：不是“最多2格”，而是“恰好2格”）。这并非标准的四邻接图遍历，而是一个自定义边规则的隐式图：每个水单元是图的节点，节点间存在有向边当且仅当满足位移约束且目标格也为水。

因此，解决方案需分两层设计：

1. 合法性预检：快速排除明显不可达情况（越界、起点/终点非水、位移不满足 |Δr|=2 且 Δc=0 或 |Δc|=1 且 Δr=0）；
2. 图搜索验证：使用深度优先搜索（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)，鲁棒性强，完全契合题意。图算法思想在此体现为：将“单步移动”抽象为带约束的边存在性判断，而非盲目遍历。

以上就是《如何用图算法解决船的移动问题 》的详细内容，更多关于的资料请关注golang学习网公众号！