点击刷新
题目描述：
给定一个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; }
© 著作权归作者所有
举报
发表评论
0/200
