四川网站建设一站式服务商,网站meta网页描述,南山区住房和建设局网站,wordpress 初始化迷宫寻路
题目描述
机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n m n\times m nm 矩阵#xff0c;每个位置要么是空地#xff0c;要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置#xff0c;问能否…迷宫寻路
题目描述
机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n × m n\times m n×m 矩阵每个位置要么是空地要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置问能否走到 ( n , m ) (n, m) (n,m) 位置。
输入格式
第一行两个正整数 n , m n,m n,m。
接下来 n n n 行输入这个迷宫。每行输入一个长为 m m m 的字符串# 表示墙. 表示空地。
输出格式
仅一行一个字符串。如果机器猫能走到 ( n , m ) (n, m) (n,m)则输出 Yes否则输出 No。
样例 #1
样例输入 #1
3 5
.##.#
.#...
...#.样例输出 #1
Yes提示
样例解释
路线如下 ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 3 , 2 ) → ( 3 , 3 ) → ( 2 , 3 ) → ( 2 , 4 ) → ( 2 , 5 ) → ( 3 , 5 ) (1,1)\to (2,1) \to (3,1) \to (3,2)\to (3,3) \to (2, 3) \to (2, 4) \to (2, 5) \to (3, 5) (1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)
数据规模与约定
对于 100 % 100\% 100% 的数据保证 1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1≤n,m≤100且 ( 1 , 1 ) (1,1) (1,1) 和 ( n , m ) (n, m) (n,m) 均为空地。 运用bfs来解决 一开始机器猫在00位置要走到n-1m-1位置 边界条件x、y大于0且分别小于n、m每一点都只能走一次(通过bool数组记载是否走过)下一次要走的位置上不是#。 #includebits/stdc.h
using namespace std;int n,m;
const int N 110;
char path[N][N];
bool st[N][N];
int X[4] {-1,0,1,0};
int Y[4] {0,-1,0,1};bool bfs()
{//BFS使用一个队列来存储待访问的节点。//队列的特性是先进先出(FIFO)这确保了BFS是逐层访问节点的。queuepairint,int q;//创建一个队列来存储待访问节点q.push({0,0});//将起始节点(0,0)入队st[0][0] true;//标记起始节点为已访问while(!q.empty())//当队列不为空时继续搜索{int x q.front().first;//取出队列中的第一个节点的坐标int y q.front().second;q.pop();//弹出队列中的第一个节点if(x n-1 y m-1)//如果当前节点是目标节点则返回 true{return true;}//遍历当前节点的四个相邻方向for(int i 0;i 4;i){int dx x X[i];//计算新节点的 x 坐标int dy y Y[i];//计算新节点的 y 坐标//检查新节点是否在网格范围内、是否未被访问过、以及是否是可通过的节点if(dx 0 dy 0 dx n dy m !st[dx][dy] path[dx][dy] ! #){st[dx][dy] true;//标记新节点为已访问q.push({dx,dy});//将新节点加入队列以便后续访问它的相邻节点}}}return false;//如果队列为空且没有找到目标节点则返回 false
}int main()
{cin n m;for(int i 0;i n;i){for(int j 0;j m;j){cin path[i][j];st[i][j] false;}}if(bfs()){cout Yes endl;}else{cout No endl;}return 0;
}
扩展
获取单一行走路径
#includebits/stdc.h
using namespace std;int n, m;
const int N 110;
char path[N][N];
bool st[N][N];
pairint, int previous[N][N]; // 用于记录每个节点的父节点
int X[4] {-1, 0, 1, 0};
int Y[4] {0, -1, 0, 1};bool bfs() {queuepairint, int q;q.push({0, 0});st[0][0] true;while (!q.empty()) {int x q.front().first;int y q.front().second;q.pop();if (x n - 1 y m - 1) {return true; // 找到目标节点返回true表示找到路径}for (int i 0; i 4; i) {int dx x X[i];int dy y Y[i];if (dx 0 dy 0 dx n dy m !st[dx][dy] path[dx][dy] ! #) {st[dx][dy] true;previous[dx][dy] {x, y}; // 记录父节点q.push({dx, dy});}}}return false; // 无法到达目标节点
}void printPath() {int x n - 1, y m - 1;vectorpairint, int path;// 回溯到起点构建路径while (x ! 0 || y ! 0) {path.push_back({x, y});pairint, int p previous[x][y];x p.first;y p.second;}path.push_back({0, 0}); // 添加起点// 打印路径从起点到终点for (int i path.size() - 1; i 0; i--) {cout ( path[i].first , path[i].second ) ;}cout endl;
}int main() {cin n m;for (int i 0; i n; i) {for (int j 0; j m; j) {cin path[i][j];st[i][j] false;previous[i][j] {-1, -1}; // 初始化为无效值}}if (bfs()) {cout Yes endl;printPath(); // 打印路径} else {cout No endl;}return 0;
}
在这段代码中增加了一个previous数组来记录每个节点的父节点。当找到目标节点时bfs函数返回true然后调用printPath函数来回溯并打印出从起点到终点的路径。 bfs部分详解
void printPath() { int x n - 1, y m - 1; // 从终点开始回溯 vectorpairint, int path; // 用于存储路径上的节点坐标 // 回溯到起点构建路径 while (x ! 0 || y ! 0) { // 当还没有回溯到起点时继续循环 path.push_back({x, y}); // 将当前节点坐标添加到路径中 pairint, int p previous[x][y]; // 获取当前节点的父节点坐标 x p.first; // 更新x坐标为父节点的x坐标 y p.second; // 更新y坐标为父节点的y坐标 } path.push_back({0, 0}); // 添加起点到路径中因为上面的循环条件导致起点不会被添加 // 打印路径从起点到终点注意这里是从后往前打印因为路径是从起点开始记录的 for (int i path.size() - 1; i 0; i--) { cout ( path[i].first , path[i].second ) ; // 打印每个节点的坐标 } cout endl; // 打印换行
}printPath 函数是用于打印从起点0,0到终点n-1, m-1在迷宫中的具体路径的。这个函数通过回溯的方式利用在广度优先搜索BFS过程中记录的每个节点的父节点信息来重建整条路径。 这个函数的工作流程如下
初始化终点坐标 (x, y) 为 (n-1, m-1)。创建一个空的 vector 容器 path用于存储路径上的节点坐标。使用 while 循环进行回溯条件是当前节点不是起点即 x ! 0 || y ! 0。 在循环中首先将当前节点的坐标 (x, y) 添加到 path 中。然后通过查询 prev 数组获取当前节点的父节点坐标并将父节点坐标赋值给 (x, y)以便在下一次循环中继续回溯。 循环结束后将起点坐标 (0, 0) 添加到 path 中因为回溯过程是从终点开始到起点结束但由于循环条件的限制起点并未被包含在内所以需要手动添加。最后使用 for 循环逆序打印 path 中的节点坐标。这是因为路径在 path 中是以从终点到起点的顺序存储的而我们需要按照从起点到终点的顺序打印出来。
通过这个函数我们就可以在控制台上看到从起点到终点的完整路径了。
