給定一個n* m大小的迷宮，其中* 代表不可通過的墻壁，而“.”代表平地，S表示起點，T代表終點，
移動程序中，如果當前位置是(x, y)(下標從0開始)，且每次只能前往上下左右、(x, y + 1)、(x, y - 1)、(x - 1, y)、(x + 1, y)四個位置的平地，求從起點S到達終點T的最少步數，
上面樣例S為(2, 2)，T的坐標為(4, 3)，
在本題中，由于求的是最少步數，而BFS是通過層次的順序來遍歷的，因此可以從起點S開始計數遍歷的層數，那么在到達終點T時的層數就是需要求解的起點S到達終點T的最少步數，
. . . . . . * . * . . * S * . . * * * . . . . T *
若使用BFS：
#include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn = 100; int n, m; char maze[maxn][maxn]; bool inq[maxn][maxn] = { false }; struct node { int x; int y; int step; }S, T, Node; int X[4] = { 0,0,1,-1 };//增量陣列便于遍歷四周節點 int Y[4] = { 1,-1,0,0 }; bool Isgo(int x, int y) { if (maze[x][y] == '*') return false; else if (x >= n || x < 0 || y >= m || y < 0 || inq[x][y] == true) return false; else return true; } int BFS() { queue<node> q; q.push(S); while (!q.empty()) { node top = q.front();//最前面的元素出隊 q.pop(); if (top.x == T.x && top.y == T.y) { return top.step;//結束點 } for (int i = 0; i < 4; i++) { int newX = top.x + X[i]; int newY = top.y + Y[i]; if (Isgo(newX, newY)) { Node.step = top.step + 1; Node.x = newX; Node.y = newY; q.push(Node);//符合條件的點全部入隊 inq[Node.x][Node.y] = true; } } } return -1;//沒有找到回傳一個-1； } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { getchar();//過濾掉每一行后面的換行符 for (int j = 0; j < m; j++) { maze[i][j] = getchar(); } maze[i][m] = '\0';//每一行結尾需要加一個'\0'字符 } scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y); S.step = 0; printf("%d\n", BFS()); return 0; }
若使用DFS：
#include<cstdio> using namespace std; const int maxn = 100; int m, n;//行數，列數 char maze[maxn][maxn];//構建的迷宮 bool mark[maxn][maxn] = { false };//用一個陣列標記是否進行訪問過 struct node { int x, y; int step; }S, Node, T; int X[4] = { 0,0,1,-1 };//設定一個增量陣列方便遍歷四周 int Y[4] = { 1,-1,0,0 }; bool Isgo(int x, int y) { if (x < 0 || x >= m || y < 0 || y >= n || mark[x][y] == true) return false; else if (maze[x][y] == '*') return false; else return true; } void DFS(int x, int y, int step) {//step記錄當前走的步數 if (x == T.x && y == T.y) { return;//到達遞回基,到達終點 } mark[x][y] = true;//訪問過便標記true for (int i = 0; i < 4; i++) { int newX = x + X[i]; int newY = y + Y[i]; if (Isgo(newX, newY)) {//進行判斷是否是可行位置 Node.x = newX; Node.y = newY; Node.step = step + 1;//步數加一 DFS(Node.x, Node.y, Node.step);//進行下一個可行的位置的遞回 } } } int main() { scanf("%d%d", &m, &n);//輸入行數和列數， for (int i = 0; i < m; i++) { getchar(); for (int j = 0; j < n; j++) { maze[i][j] = getchar();//過濾掉每一行后面的換行符 } maze[i][n] = '\0';//每一行應該以'\0'結尾 } scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y);//輸入起點和終點 S.step = 0; DFS(S.x, S.y, S.step); printf("%d", Node.step); return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279787.html
標籤：其他
上一篇：廣度優先搜索（BFS）