N×M网格中马与主教可相遇位置求解及时间复杂度计算

问题核心 #

在N行M列的带障碍网格中，找到任意一个马和主教都能到达的合法位置即可。

移动规则明确 #

• 马的移动：每次走日字，共8个移动偏移量：[(-2,-1), (-2,1), (-1,-2), (-1,2), (1,-2), (1,2), (2,-1), (2,1)]，移动后不能出界、不能落在障碍格
• 主教的移动：每次沿对角线走任意步数，路径上不能有障碍，落点不能出界、不能是障碍格

核心算法思路 #

采用两次广度优先搜索（BFS）分别统计两个角色的可达点集合，取交集返回任意元素即可：

1. 第一次从马的初始位置出发BFS，记录所有马能到达的合法格子
2. 第二次从主教的初始位置出发BFS，记录所有主教能到达的合法格子
3. 遍历两个可达集合的交集，返回第一个遇到的位置

数据结构设计 #

• 障碍网格：二维布尔数组blocked[N][M]，blocked[i][j]为True表示该位置是无效障碍格
• 可达性标记：两个二维布尔数组horse_reach[N][M]、bishop_reach[N][M]，分别标记对应角色是否可达该位置
• BFS队列：用双向队列存储待遍历的坐标，保证O(1)的头尾操作效率

代码实现（Python） #

from collections import deque

def find_meet_point(n, m, blocked, horse_start, bishop_start):
    # 马的8个移动方向
    horse_dirs = [(-2,-1), (-2,1), (-1,-2), (-1,2), (1,-2), (1,2), (2,-1), (2,1)]
    # 主教的4个对角线方向
    bishop_dirs = [(-1,-1), (-1,1), (1,-1), (1,1)]

    # 计算马的可达点
    horse_reach = [[False]*m for _ in range(n)]
    q = deque()
    hx, hy = horse_start
    if not blocked[hx][hy]:
        horse_reach[hx][hy] = True
        q.append((hx, hy))
    while q:
        x, y = q.popleft()
        for dx, dy in horse_dirs:
            nx = x + dx
            ny = y + dy
            if 0<=nx<n and 0<=ny<m and not blocked[nx][ny] and not horse_reach[nx][ny]:
                horse_reach[nx][ny] = True
                q.append((nx, ny))
    
    # 计算主教的可达点
    bishop_reach = [[False]*m for _ in range(n)]
    q = deque()
    bx, by = bishop_start
    if not blocked[bx][by]:
        bishop_reach[bx][by] = True
        q.append((bx, by))
    while q:
        x, y = q.popleft()
        for dx, dy in bishop_dirs:
            # 沿当前对角线一直走，直到出界或遇到障碍
            nx, ny = x + dx, y + dy
            while 0<=nx<n and 0<=ny<m and not blocked[nx][ny]:
                if not bishop_reach[nx][ny]:
                    bishop_reach[nx][ny] = True
                    q.append((nx, ny))
                nx += dx
                ny += dy
    
    # 查找共同可达点
    for i in range(n):
        for j in range(m):
            if horse_reach[i][j] and bishop_reach[i][j]:
                return (i,j)
    # 无共同可达点返回空
    return None

# 测试用例
if __name__ == "__main__":
    N, M = 7,7
    blocked = [[False]*M for _ in range(N)]
    # 示例给出的无效格
    blocked[0][3] = True
    blocked[2][0] = True
    horse_start = (6,6)
    bishop_start = (3,2)
    res = find_meet_point(N, M, blocked, horse_start, bishop_start)
    print(f"相遇点：{res}") # 输出结果包含示例的(4,5)

时间复杂度计算 #

• 马的BFS：每个格子最多入队一次，每个格子处理8个方向，时间复杂度为O(N×M)
• 主教的BFS：每个格子最多入队一次，每个格子沿四个对角线遍历，每个格子最多被4个方向的路径扫到一次，总遍历次数也是O(N×M)
• 交集查找：遍历整个网格，时间复杂度O(N×M)
• 整体时间复杂度为O(N×M)，和网格规模线性相关

优化提示 #

可以利用主教对角线移动不会改变棋盘染色属性的特点提前剪枝：如果马的可达集合里没有和主教初始位置同色的格子，直接返回无结果，不需要执行后续遍历。

内容的提问来源于stack exchange，提问作者Sourabh sahu