程序员的算法趣题Q26: 高效的立体停车场

1. 问题描述

最近，一些公寓等建筑也都配备了立体停车场。立体停车场可以充分利用窄小的土地，通过上下左右移动来停车、出库，从而尽可能多地停车。

现在有一个立体停车场，车出库时是把车往没有车的位置移动，从而把某台车移动到出库位置。假设要把左上角的车移动到右下角，试找出路径最短时的操作步数。

举个例子，在 3×2的停车场用如图13所示的方式移动时，需要移动13步。

图1车从左上角移动到右下角的示例1（13步）

不过，如果用如下图所示的移动方法，则只需要移动 9步。

图2车从左上角移动到右下角的示例1（9步）

问题：

求在 10×10的停车场中，把车从左上角移动到右下角时按最短路径移动时需要的最少步数。

2. 解题分析

因为是求最短路径，所以可以用广度优先搜索策略来解决。

广度优先搜索有与深度优先搜索相同的三个基本要素：

1. 基本算法流程
2. 状态表示方法
3. 遍历下一个状态

其中(2)和(3)相关联的，合理的状态表示和遍历方法的选择是解决问题的效率的关键。

2.1 BFS基本流程

2.2 状态表示方法

本题考虑以车和空位的位置坐标表示当前状态（或节点），再加上对应的层数，即[[x1,y1, x2,y2], layer].其中[x1,y1]表示车的位置，[x2,y2]表示空位的位置。

车的其实位置为[0,0], 空位的其实坐标为[N-1,M-1]，N和M分别为车库的行数和列数。

当车的位置移动到[N-1,M-1]，即算到达目标。

2.3 遍历下一个状态

本问题搜索下一个状态（或者说移动方式）是一件麻烦事。

焦点是空位的移动。因为空位是一定移动的，车则不一定，车只有在与空位相邻的时候才有机会移动。要点如下：

1. 空位在中心位置的话，有4个方向都可以移动
2. 空位在边缘的话就会受到限制
3. 如果车恰好在空位某个方向的相邻位置，则空位往这个方向的移动是交换车和空位的位置

参见findNext()函数。本题解中findNext()函数写得比较冗长，暂时没有想到更简洁的写法。不过这个不是关键点，暂时将就一下。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Mon Sep 13 07:10:26 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
from   collections import deque
import itertools as it

class Solution:
    def parkingMove(self,N,M):
        
        '''    
        The content stored in Queue:
            [[x1,y1,x2,y2], layer]. (x1,y1): car position; (x2,y2): empty position
        'visited' is implemented as dict() for faster item search, the value is irrelant, hence set to ''.
        (x1,y1,x2,y2) is used as the key of 'visited', instead of [x1,y1,x2,y2], because list is unhashable type.
                
        Returns
        -------
            The number of moves needed to move car to the right-down lot, from top-left lot.
        '''

        def findNext(curState):                        
            nxtStateLst = []
            # empty up
            carPos,emptyPos   = curState[0:2], curState[2:]
            if emptyPos[0] > 0:
                # print('up')
                if carPos[0] == emptyPos[0] - 1 and carPos[1] == emptyPos[1]:                    
                    carPos[0]   = carPos[0] + 1
                emptyPos[0] = emptyPos[0] - 1                    
                nxtStateLst.append(carPos+emptyPos)
            # empty down
            carPos,emptyPos   = curState[0:2], curState[2:]
            if emptyPos[0] < N-1:
                # print('down')
                if carPos[0] == emptyPos[0] + 1 and carPos[1] == emptyPos[1]:                    
                    carPos[0]   = carPos[0] - 1
                emptyPos[0] = emptyPos[0] + 1      
                nxtStateLst.append(carPos+emptyPos)                          
            # empty left
            carPos,emptyPos   = curState[0:2], curState[2:]
            if emptyPos[1] > 0:
                # print('left')
                if carPos[1] == emptyPos[1] - 1 and carPos[0] == emptyPos[0]:                    
                    carPos[1]   = carPos[1] + 1
                emptyPos[1] = emptyPos[1] - 1                                
                nxtStateLst.append(carPos+emptyPos)
            # empty right
            carPos,emptyPos   = curState[0:2], curState[2:]
            if emptyPos[1] < M-1:
                # print('right')
                if carPos[1] == emptyPos[1] + 1 and carPos[0] == emptyPos[0]:                    
                    carPos[1]   = carPos[1] - 1
                emptyPos[1] = emptyPos[1] + 1      
                nxtStateLst.append(carPos+emptyPos)                                      
            # print('findNext: ',curState,' -> ',nxtStateLst)                
            return nxtStateLst
        
        # Initialization
        q = deque()
        visited = dict()
        car_start, empty_start = [0,0], [N-1,M-1]
        car_target = [N-1,M-1]
        
        q.append([car_start + empty_start, 0])
        visited[tuple(car_start + empty_start)] = ''
    
        while len(q) != 0:
            node = q.popleft()            
            # print(node)
            car_pos = node[0][0:2]
            layer   = node[1]
            if car_pos == car_target:
                return layer
            
            nxtStateLst = findNext(node[0])
            for nxtState in nxtStateLst:
                if tuple(nxtState) not in visited:
                    visited[tuple(nxtState)] = ''
                    q.append([nxtState, layer+1])
                            
    
if __name__ == '__main__':      

    sln     = Solution()   
    tStart  = time.perf_counter()
    N,M     = 10,10 # N*M parking-lots
    numOfMoves = sln.parkingMove(N,M)
    tCost   = time.perf_counter() - tStart
    print('N,M={0},{1}, num-of-moves = {2}, tCost = {3:6.3f}(sec)'.format(N,M,numOfMoves,tCost))

运行结果：

N,M=10,10, num-of-moves = 69, tCost = 0.145(sec)

4. 后记

以上题解中用deque来实现队列，需要注意的一点是，deque是双向队列，其入队离队方法为append(), pop(), appendleft(), popleft()，其中append()与popleft()构成一对，appendleft()与pop()构成一对。如果配错对了就不是队列而变成栈了，那就得不到最短距离解了。