題目描述：

又是晴朗的一天，牛牛的小伙伴們都跑來找牛牛去公園玩。但是牛牛想呆在家里看E3展，不想出去逛公園，可是牛牛又不想鴿掉他的小伙伴們，于是找來了公園的地圖，發現公園是由一個邊長為n的正方形構成的，公園一共有m個入口，但出口只有一個。公園內有一些湖和建筑，牛牛和他的小伙伴們肯定不能從他們中間穿過，所以只能繞行。牛牛想知道他需要走的最短距離并輸出這個最短距離。

第一行輸入一個數字n(1≤n≤1000)表示公園的邊長接下來會給你一個n*n的公園地圖，其中 . 表示公園里的道路，@?表示公園的入口，* 表示公園的出口，# 表示公園內的湖和建筑。牛牛和他的小伙伴們每次只能上下左右移動一格位置。輸入保證公園入口個數m(1≤m≤10000)且所有的入口都能和出口相連。

輸入
10
mat = [['.', '@', '.', '.', '.', '.', '#', '#', '@', '.'],['.', '.', '.', '.', '.', '.', '#', '.', '.', '.'],['.', '.', '.', '@', '.', '.', '#', '.', '.', '.'],['#', '#', '#', '.', '.', '.', '.', '.', '.', '.'],['.', '.', '.', '.', '#', '#', '.', '.', '#', '.'],['.', '.', '.', '#', '#', '#', '#', '.', '.', '.'],['@', '.', '.', '.', '#', '#', '.', '.', '.', '.'],['#', '#', '#', '#', '#', '.', '.', '.', '.', '.'],['.', '.', '#', '#', '*', '#', '#', '#', '#', '.'],['#', '.', '.', '.', '.', '.', '.', '.', '.', '.']] 輸出

16

問題分析：廣度優先搜索（Breadth First Search，BFS）

采用廣度優先搜索的思想，首先每找到一個入口，進行一次廣度優先搜索，用隊列實現，但是每次出隊的時候，并不是真正的出隊，只讓隊頭指針向后移動一次，這是為了，在找到出口的時候回溯到起點，以便求出最短路徑，所以在入隊的時候，要記錄前一個結點的位置用于回溯。

Python3實現：

# 廣度優先搜索，隊列實現 # @Time :2018/6/20 # @Author :LiuYinxingdef findpath(mat, n, row, col):path = [[1]*n for _ in range(n)]path[row][col] = 0 # 初始化隊頭pre = -1qlist = [[row, col, pre]]while qlist:pre += 1 # 出隊i, j = qlist[pre][0], qlist[pre][1]if -1 < i-1: # 上if path[i-1][j] == 1 and mat[i-1][j] == '.':qlist.append([i-1, j, pre]) # 入隊path[i-1][j] = 0 # 標記一下，已經走過了elif path[i-1][j] == 1 and mat[i-1][j] == '*': # 出口qlist.append([i - 1, j, pre]) # 入隊breakif j+1 < n: # 右if path[i][j+1] == 1 and mat[i][j+1] == '.':qlist.append([i, j+1, pre])path[i][j+1] = 0elif path[i][j+1] == 1 and mat[i][j+1] == '*':qlist.append([i, j+1, pre])breakif i+1 < n: # 下if path[i+1][j] == 1 and mat[i+1][j] == '.':qlist.append([i+1, j, pre])path[i+1][j] = 0elif path[i+1][j] == 1 and mat[i+1][j] == '*':qlist.append([i + 1, j, pre])breakif j-1 > -1: # 左if path[i][j-1] == 1 and mat[i][j-1] == '.':qlist.append([i, j-1, pre])path[i][j-1] = 0elif path[i][j-1] == 1 and mat[i][j-1] == '*':qlist.append([i, j-1, pre])breakfpath = [qlist[-1]] # 回溯計算最短路徑while pre != -1:fpath.append(qlist[pre])pre = qlist[pre][2]print(len(fpath)-1, fpath[::-1])return len(fpath)-1def minpath(mat, n): # 獲取所有入口的最短路徑，并且選擇小的一個minpath = float('inf')for i in range(n):for j in range(n):if mat[i][j] == '@':minpath = min(findpath(mat, n, i, j), minpath)print('最短路徑長度為:', minpath)if __name__ == '__main__':n, m = 10, 4mat = [['.', '@', '.', '.', '.', '.', '#', '#', '@', '.'],['.', '.', '.', '.', '.', '.', '#', '.', '.', '.'],['.', '.', '.', '@', '.', '.', '#', '.', '.', '.'],['#', '#', '#', '.', '.', '.', '.', '.', '.', '.'],['.', '.', '.', '.', '#', '#', '.', '.', '#', '.'],['.', '.', '.', '#', '#', '#', '#', '.', '.', '.'],['@', '.', '.', '.', '#', '#', '.', '.', '.', '.'],['#', '#', '#', '#', '#', '.', '.', '.', '.', '.'],['.', '.', '#', '#', '*', '#', '#', '#', '#', '.'],['#', '.', '.', '.', '.', '.', '.', '.', '.', '.']]minpath(mat, n)

Python3（簡化代碼）：

# 廣度優先搜索，隊列實現 # @Time :2018/6/20 # @Author :LiuYinxingdef findpath(mat, n, row, col):path = [[1]*n for _ in range(n)]path[row][col] = 0 # 初始化隊頭pre = -1qlist = [[row, col, pre]]while qlist:pre += 1 # 出隊i, j = qlist[pre][0], qlist[pre][1]if checkplace(mat, path, qlist, n, pre, i-1, j): break # 上if checkplace(mat, path, qlist, n, pre, i, j+1): break # 右if checkplace(mat, path, qlist, n, pre, i+1, j): break # 下if checkplace(mat, path, qlist, n, pre, i, j-1): break # 左fpath = [qlist[-1]] # 回溯計算最短路徑while pre != -1:fpath.append(qlist[pre])pre = qlist[pre][2]print(len(fpath)-1, fpath[::-1])return len(fpath)-1def checkplace(mat, path, qlist, n, pre, row, col): # 判斷新節點是否是出口if -1 < row < n and -1 < col < n and path[row][col] == 1:if mat[row][col] == '.':qlist.append([row, col, pre]) # 入隊path[row][col] = 0elif mat[row][col] == '*': # 出口qlist.append([row, col, pre]) # 入隊return 1def minpath(mat, n): # 獲取所有入口的最短路徑，并且選擇小的一個minpath = float('inf')for i in range(n):for j in range(n):if mat[i][j] == '@':minpath = min(findpath(mat, n, i, j), minpath)print('最短路徑長度為:', minpath)if __name__ == '__main__':n, m = 10, 4mat = [['.', '@', '.', '.', '.', '.', '#', '#', '@', '.'],['.', '.', '.', '.', '.', '.', '#', '.', '.', '.'],['.', '.', '.', '@', '.', '.', '#', '.', '.', '.'],['#', '#', '#', '.', '.', '.', '.', '.', '.', '.'],['.', '.', '.', '.', '#', '#', '.', '.', '#', '.'],['.', '.', '.', '#', '#', '#', '#', '.', '.', '.'],['@', '.', '.', '.', '#', '#', '.', '.', '.', '.'],['#', '#', '#', '#', '#', '.', '.', '.', '.', '.'],['.', '.', '#', '#', '*', '#', '#', '#', '#', '.'],['#', '.', '.', '.', '.', '.', '.', '.', '.', '.']]minpath(mat, n)歡迎指正哦。

總結

以上是生活随笔為你收集整理的牛客网IT校招编程题-逛公园-Python的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。