城堡漫步編程題目及答案題目描述：在一個古老的城堡中，有一條蜿蜒曲折的長廊，長廊被分成了若干個房間，每個房間之間通過門相連。現(xiàn)在，你需要編寫一個程序，模擬一個人從長廊的起點(diǎn)開始漫步，直到到達(dá)長廊的終點(diǎn)。每個房間的門可以是開啟的也可以是關(guān)閉的，如果門是關(guān)閉的，則無法通過。你需要計算出從起點(diǎn)到終點(diǎn)的最短路徑長度。輸入：-第一行包含兩個整數(shù)`n`和`m`，分別表示房間的數(shù)量和門的數(shù)量。-接下來的`m`行，每行包含兩個整數(shù)`x`和`y`，表示房間`x`和`y`之間有一扇門，門可以是開啟的也可以是關(guān)閉的。如果門是開啟的，則`x`和`y`之間沒有障礙，可以自由通過。輸出：-輸出一個整數(shù)，表示從起點(diǎn)到終點(diǎn)的最短路徑長度。如果無法到達(dá)終點(diǎn)，則輸出`-1`。示例輸入：```4412233414```示例輸出：```2```分析：這個問題可以通過圖論中的最短路徑算法來解決，例如使用廣度優(yōu)先搜索（BFS）算法。我們可以將每個房間看作圖中的一個節(jié)點(diǎn)，每扇門看作圖中的一條邊。然后，從起點(diǎn)開始，使用BFS遍歷圖，直到找到終點(diǎn)或者無法到達(dá)終點(diǎn)。解答：```pythonfromcollectionsimportdequedefbfs_shortest_path(n,m,doors):創(chuàng)建圖的鄰接表graph={i:[]foriinrange(1,n+1)}forx,yindoors:graph[x].append(y)graph[y].append(x)初始化隊(duì)列和訪問標(biāo)記queue=deque([(1,0)])(節(jié)點(diǎn),路徑長度)visited=set()whilequeue:current,path_length=queue.popleft()ifcurrent==n:returnpath_lengthifcurrentnotinvisited:visited.add(current)forneighboringraph[current]:ifneighbornotinvisited:queue.append((neighbor,path_length+1))return-1讀取輸入n,m=map(int,input().split())doors=[tuple(map(int,input().split()))for_inrange(m)]計算最短路徑shortest_path=bfs_shortest_path(n,m,doors)print(shortest_path)```解釋：1.首先，我們創(chuàng)建了一個圖的鄰接表，用于存儲每個房間（節(jié)點(diǎn)）與其相連的房間（節(jié)點(diǎn)）。2.使用廣度優(yōu)先搜索（BFS）算法，從起點(diǎn)（房間1）開始遍歷圖。3.我們使用一個隊(duì)列來存儲待訪問的節(jié)點(diǎn)及其對應(yīng)的路徑長度。4.每次從隊(duì)列中取出一個節(jié)點(diǎn)，如果該節(jié)點(diǎn)是終點(diǎn)，則返回當(dāng)前的路徑長度。5.如果該節(jié)點(diǎn)未被訪問過，將其標(biāo)記為已訪問，并將其相鄰的節(jié)點(diǎn)加入隊(duì)列中