【題目鏈接】

ybt 1252：走迷宮
OpenJudge NOI 2.5 2753:走迷宮

【題目考點】

1. 廣搜 迷宮問題

【解題思路】

設結構體類型的結點保存位置以及步數，隊列中保存的是該結構體類型的變量。設vis數組記錄一個位置是否已經訪問過。
廣搜借助隊列，首先起點位置入隊，而后每次出隊一個位置，將該位置可以到達的所有與之相鄰的位置入隊，同時記錄行走步數。如果到達終點位置，輸出到達終點時的步數即為從起點到終點的最短距離。
做廣搜時一定要堅持：先訪問再入隊，出隊時判斷解。
訪問一個位置，指該位置在vis數組中設為true。如果出隊時再訪問，可能會出現重復訪問的情況。判斷解指判斷該位置是否為終點。

【題解代碼】

解法1：廣搜

#include <bits/stdc++.h> using namespace std; #define N 45 struct Node//設置結點 {int x, y, s;//到(x,y)位置是步數為s Node(){}Node(int a, int b, int c):x(a), y(b), s(c){} }; int r, c;//行、列 char mp[N][N];//地圖 bool vis[N][N];//vis[i][j]表示第i，j位置是否已訪問過 int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; //方向數組 int bfs()//廣搜，返回從左上角走到右下角的最少步數 {queue<Node> que;vis[1][1] = true;//訪問初始位置que.push(Node(1, 1, 1));while(que.empty() == false)//如果隊列不空{Node u = que.front();que.pop();//出隊一個結點if(u.x== r && u.y == c)//如果到終點return u.s;//返回終點結點上的步數for(int i = 0; i < 4; ++i)//遍歷四個方向上的位置{int x = u.x + dir[i][0], y = u.y + dir[i][1], s = u.s + 1;//新的位置，以及步數if(x >= 1 && x <= r && y >= 1 && y <= c && vis[x][y] == false && mp[x][y] == '.'){//如果在范圍內 且 沒訪問過 且 這個位置是空地vis[x][y] = true;//訪問x，y位置que.push(Node(x, y, s));//該位置及步數構成結點，入隊}}} } int main() {cin >> r >> c;for(int i = 1; i <= r; ++i)for(int j = 1; j <= c; ++j)cin >> mp[i][j];cout << bfs();return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1252：走迷宫 | OpenJudge NOI 2.5 2753:走迷宫的全部內容，希望文章能夠幫你解決所遇到的問題。

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