用ae做模板下载网站,建设网站 软件,百度搜索优化,阿里云官方网站 icp代备案管理系统题目传送门#xff1a;迷宫寻路 - 洛谷
大意
给定一个 nm 的矩阵#xff0c;每个位置要么是空地#xff0c;要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 (1,1)(1,1) 的位置#xff0c;问能否走到 (n,m) 位置。
代码
广搜模板题迷宫寻路 - 洛谷
大意
给定一个 n×m 的矩阵每个位置要么是空地要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 (1,1)(1,1) 的位置问能否走到 (n,m) 位置。
代码
广搜模板题可以看注释
#includeiostream
#includequeue
using namespace std;
#define For(i, j, k) for(int i j; i k; i)
#define dFor(i, j, k)for(int i j; i k; i--)
#define MaxN 105int n, m, flag;
char a[MaxN][MaxN];
int dx[] {0, 0, -1, 1};
int dy[] {1, -1, 0, 0};
int vis[MaxN][MaxN];int check(int x, int y){ //依旧是check函数return !(x1||xn||y1||ym) a[x][y] ! # !vis[x][y];
}void bfs(){queueint qx, qy; //搜索队列qx.push(1); qy.push(1); //先搜索11vis[1][1] 1; //vis储存是否被访问过while(!qx.empty()){int x qx.front();int y qy.front();qx.pop(); qy.pop();//取出队列最上方元素For(i, 0, 3){int tx x dx[i]; //要搜点的xy坐标int ty y dy[i];
// cout tx ty endl;if(tx n ty m){flag 1; return ;//已经搜索到了直接返回}if(check(tx, ty)){qx.push(tx);qy.push(ty);//合法将其加入搜索队列vis[tx][ty] 1;}}}
}int main()
{cin n m;For(i, 1, n){For(j, 1, m){cin a[i][j];}}bfs();if(flag) cout Yes\n;else cout No\n;return 0;
}
总结
模板题没什么好说的当个板子看看就行了
