程序员的算法趣题Q63: 迷宫会合

1. 问题描述

2. 解题分析

5*5的网格共有25个格子，每个格子有两个可能（墙壁或通道），共有2^25=33554432种。但是，并非每种都能构成有效的迷宫。相当惊人的一个基数，没有有效的缩小范围或者计算优化策略的话，会需要话很长的时间。

2.1 有效的迷宫

有效的迷宫是指入口（左上角）到出口（右下角）是连通的。因此判断某种通道/墙壁排列是否有效可以作为Reachability问题来处理，可以用广度优先搜索来进行判断。代码如下（注意0表示墙壁，1表示通道，而且为了方便判断，外加一圈围栏，围栏全部初始化为墙壁）：

def is_valid_maze(maze):
    '''
    Check the reachability from [1,1] to [N,N], using BFS algorithm
    '''
    start = (1,1)
    target = (N,N)
        
    curMaze = maze.copy()            
    s = deque() # Used as stack, LIFO
    s.append(start)
    is_valid = False
    while len(s) > 0:
        cur = s.pop()
        if cur == target:
            is_valid = True
        # print(cur)
        curMaze[cur[0],cur[1]] = 0 # Flag it to indicate that it has already been visited.
        if curMaze[cur[0]-1,cur[1]] == 1: # Up grid
            s.append((cur[0]-1,cur[1]))
        if curMaze[cur[0]+1,cur[1]] == 1: # Down grid
            s.append((cur[0]+1,cur[1]))
        if curMaze[cur[0],cur[1]-1] == 1: # Left grid
            s.append((cur[0],cur[1]-1))
        if curMaze[cur[0],cur[1]+1] == 1: # Right grid
            s.append((cur[0],cur[1]+1))        
    return is_valid

2.2 移动

根据题意，在迷宫中A和B都必须按照“右手法则前进”，这意味着，在任何一个地方，

注意，前后左右是一个相对的概念，取决于人当时的朝向。因此：

由此可得代码如下（相当直白冗长，无暇优化^-^）：

def move(A, prev_dir):
    '''
     prev_dir: 0:down, 1: right, 2: up; 3: left
    '''
    if prev_dir == 0: # down 
        if maze[A[0],A[1]-1] == 1: # A left
            A = [A[0],A[1]-1]                    
            A_dir = 3
        elif maze[A[0]+1,A[1]] == 1: # A down
            A = [A[0]+1,A[1]]
            A_dir = 0
        elif maze[A[0],A[1]+1] == 1: # A right
            A = [A[0],A[1]+1]
            A_dir = 1
        else: #if maze[A[0]-1,A[1]] == 1: # A up
            A = [A[0]-1,A[1]]
            A_dir = 2
    elif prev_dir == 1: # right
        if maze[A[0]+1,A[1]] == 1:   # A down
            A = [A[0]+1,A[1]]            
            A_dir = 0
        elif maze[A[0],A[1]+1] == 1: # A right
            A = [A[0],A[1]+1]
            A_dir = 1
        elif maze[A[0]-1,A[1]] == 1: # A up
            A = [A[0]-1,A[1]]
            A_dir = 2
        else: #if maze[A[0],A[1]-1] == 1: # A left
            A = [A[0],A[1]-1]        
            A_dir = 3
    elif prev_dir == 2: # up
        if maze[A[0],A[1]+1] == 1: # A right
            A = [A[0],A[1]+1]
            A_dir = 1
        elif maze[A[0]-1,A[1]] == 1: # A up
            A = [A[0]-1,A[1]]
            A_dir = 2
        elif maze[A[0],A[1]-1] == 1: # A left
            A = [A[0],A[1]-1]                        
            A_dir = 3
        else: #if maze[A[0]+1,A[1]] == 1:   # A down
            A = [A[0]+1,A[1]]            
            A_dir = 0
    elif prev_dir == 3: # left
        if maze[A[0]-1,A[1]] == 1: # A up
            A = [A[0]-1,A[1]]
            A_dir = 2
        elif maze[A[0],A[1]-1] == 1: # A left
            A = [A[0],A[1]-1]                        
            A_dir = 3
        elif maze[A[0]+1,A[1]] == 1: # A down
            A = [A[0]+1,A[1]]                            
            A_dir = 0
        else: #if maze[A[0],A[1]+1] == 1: # A right
            A = [A[0],A[1]+1]                
            A_dir = 1
    return A, A_dir

2.3 能否碰上

在选定一种合法的迷宫模式后，两人是否能碰上按照以下算法进行判断：

代码如下：

def meet_or_not(maze):
    '''
    A starts from [1,1], B starts from [N,N]
    Can they meet at some grid, by reaching there at the same time?
    '''    
    A = [1,1]
    B = [N,N]
    A_dir = 3 # 0:down, 1: right, 2: up; 3: left
    B_dir = 1
    while 1:
        # print('meet_or_not: ', A, B)
        A, A_dir = move(A, A_dir)
        B, B_dir = move(B, B_dir)

        if A==B:
            # print('meet_or_not(maze) with {0}: Can meet'.format(maze))
            return True
        #if (A == [1,1]) or (A == [N,N]) or (B == [1,1]) or (B == [N,N]):
        if (A == [N,N]) or (B == [1,1]):            
            break
    # print('meet_or_not(maze) with \n{0}: Cannot meet'.format(maze))
    return False

需要注意的是，一开始受到题目描述中“所谓右手法则，就是靠着右边墙壁前进，不一定要按最短路径前进，但最终要回到入口或者到达出口”的误导，在失败判断中按以下条件处理：

if (A == [1,1]) or (A == [N,N]) or (B == [1,1]) or (B == [N,N]):

但是这个是不对的。按照右手法则，在某些特别的迷宫配置条件中，完全有可能A和/或B先回到起点然后再移动，然后再碰头。按照以上条件的话，再碰头之前回到自己出发点就判为失败了。

2.4 搜索

基于以上准备工作，搜索流程如下所示：

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Sun Oct 24 13:34:24 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
from   collections import deque
import itertools as it
import numpy as np

print(__doc__)

def is_valid_maze(maze):
    '''
    Check the reachability from [1,1] to [N,N], using BFS algorithm
    '''


def move(A, prev_dir):
    '''
     prev_dir: 0:down, 1: right, 2: up; 3: left
    '''

    
def meet_or_not(maze):
    '''
    A starts from [1,1], B starts from [N,N]
    Can they meet at some grid, by reaching there at the same time?
    '''    


# # test meet_or_not()
# N = 4
# maze = np.zeros((N+2, N+2))
# maze[1,1] = 1
# maze[1,3] = 1
# maze[2,1:5] = 1
# maze[3,1] = 1
# maze[3,3] = 1
# maze[4,2:5] = 1
# print(maze)
# print(meet_or_not(maze))


tStart  = time.perf_counter()      
N = 5
count = 0
item_cnt = 0
for item in it.product([0,1],repeat=N**2):
    item_cnt += 1
    if item_cnt%100000 == 0:
        print('item_cnt = {0}'.format(item_cnt))
    if item[0]==0 or item[N*N-1]==0:
        # The left-top and right-down corners must not be wall.
        continue
        
    # print(item)
    # Maze initialization
    # Assuming, '0' represents wall; '1' represent passage
    # Add guard for easy judge, and guard is also initialized to '0'
    maze = np.zeros((N+2, N+2))
    for k in range(N):
        for j in range(N):
            maze[k+1,j+1] = item[k*N+j]
            
    # Judge whether this maze is valid
    if not is_valid_maze(maze):
        # Not a valid maze, skip the following processing, go to the next
        # print(maze, 'invalid')
        continue 
    
    # For a valid maze, decide whether A and B can meet
    if meet_or_not(maze):
        count = count + 1
        
tCost  = time.perf_counter() - tStart
print('N={0}, count = {1}, tCost = {2:6.3f}(sec)'.format(N,count,tCost))
        

运行结果：N=5, count = 660148, tCost = 200.357(sec)

4. 后记

速度太慢了。需要进一步考虑优化方法。最近几道题目都这样，习惯了。。。^-^。不过作为普通的渣渣，不指望一蹴而就地搞定，而是先做一个可行的方案然后再来做优化比较可行吧^-^。