16.現有一個m*n的迷宮矩陣 maze(如圖 a),矩陣中有空格子(用1表示,可通行)和墻(用0表示,不可通行);在迷宮中通行的每一步移動操作,你可以往上,下,左或者右方向移動一個格子(不能進入墻所在的格子)。
你的目標是找到離entry(入口)最近的出口,并規(guī)劃入口到出口的行走路徑。(出口的含義是 maze邊界上的空格子。entry格子不算出口)。如果不存在這樣的路徑,請你返回-1;如果有,則展示entry到出口的行走路徑。
程序在正常執(zhí)行后,運行結果如圖b所示:
●尋找最近出口位置的思路與算法:
預設:0墻 1空格子 2已探索
在廣度優(yōu)先搜索的過程中,我們在隊列中保存[cx,cy,d]三元素列表,其中(cx,cy)為當前的行列坐標,d為當前坐標相對入口的距離(即需要移動的步數)。
當我們遍歷至(cx,cy)時,我們枚舉它上下左右的相鄰坐標(nx,ny)。此時可能有三種情況:
①(nx,ny)不屬于迷宮坐標或為墻,此時無需進行任何操作;
②(nx,ny)為迷宮的出口(在迷宮邊界且不為墻),此時應返回 nx,ny,d+1,即該出口的坐標以及相對入口的距離作為答案。
③(nx,ny)為空格子且不為出口,此時應將新坐標設置為已探索,并將其對應的三元素列表[nx,ny,d+1]加入隊列。
最終,如果不存在到達出口的路徑,我們返回-1作為答案。
1、若迷宮數據為maze=[[0,0,0,0,0],[1,1,1,1,0],[0,1,0,1,1],[0,1,1,1,0],[0,0,0,0,0]],則最少移動步數為
。
2、請將以下的程序代碼,補充完整。