最近,一些公寓等建筑也都配备了立体停车场。立体停车场可以充分利用窄小的土地,通过上下左右移动来停车、出库,从而尽可能多地停车。
现在有一个立体停车场,车出库时是把车往没有车的位置移动,从而把某台车移动到出库位置。假设要把左上角的车移动到右下角,试找出路径最短时的操作步数。
举个例子,在 3×2的停车场用如图13所示的方式移动时,需要移动13步。
图1车从左上角移动到右下角的示例1(13步)
不过,如果用如下图所示的移动方法,则只需要移动 9步。
图2车从左上角移动到右下角的示例1(9步)
问题:
求在 10×10的停车场中,把车从左上角移动到右下角时按最短路径移动时需要的最少步数。
因为是求最短路径,所以可以用广度优先搜索策略来解决。
广度优先搜索有与深度优先搜索相同的三个基本要素:
其中(2)和(3)相关联的,合理的状态表示和遍历方法的选择是解决问题的效率的关键。
本题考虑以车和空位的位置坐标表示当前状态(或节点),再加上对应的层数,即[[x1,y1, x2,y2], layer].其中[x1,y1]表示车的位置,[x2,y2]表示空位的位置。
车的其实位置为[0,0], 空位的其实坐标为[N-1,M-1],N和M分别为车库的行数和列数。
当车的位置移动到[N-1,M-1],即算到达目标。
本问题搜索下一个状态(或者说移动方式)是一件麻烦事。
焦点是空位的移动。因为空位是一定移动的,车则不一定,车只有在与空位相邻的时候才有机会移动。要点如下:
参见findNext()函数。本题解中findNext()函数写得比较冗长,暂时没有想到更简洁的写法。不过这个不是关键点,暂时将就一下。
- # -*- 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)
以上题解中用deque来实现队列,需要注意的一点是,deque是双向队列,其入队离队方法为append(), pop(), appendleft(), popleft(),其中append()与popleft()构成一对,appendleft()与pop()构成一对。如果配错对了就不是队列而变成栈了,那就得不到最短距离解了。