山东网站制作,网站用图怎么做文件小质量高,简述网站开发流程,wordpress建站云平台涉及知识点#xff1a;求迷宫能否到达终点的#xff0c;而不是求路径数的#xff0c;用bfs时可以不用重置状态数组#xff08;回溯#xff09;。
题目描述
给你一个n*m的迷宫#xff0c;这个迷宫中有以下几个标识#xff1a;
s代表起点
t代表终点
x代表障碍物
.代…涉及知识点求迷宫能否到达终点的而不是求路径数的用bfs时可以不用重置状态数组回溯。
题目描述
给你一个n*m的迷宫这个迷宫中有以下几个标识
s代表起点
t代表终点
x代表障碍物
.代表空地
现在你们涵哥想知道能不能从起点走到终点不碰到障碍物只能上下左右进行移动并且不能移动到已经移动过的点。
输入描述:
输入第一行一个整数T(1T10)
接下来有T组测试数据对于每一组测试数据第一行输入2个数n和m(1n,m500)
接下来n行每行m个字符代表这个迷宫每个字符都是上面4个中的一种
数据保证只有一个起点和一个终点
输出描述:
对于每一组测试数据如果可以的话输出YES不可以的话输出NO
示例1
输入
复制1 3 5 s...x x...x ...tx
1
3 5
s...x
x...x
...tx
输出
复制YES
YES
想法
用dfs求结果超时了。毕竟都500层了……
代码
#includebits/stdc.h using namespace std; int n,m; int ans; char mg[510][510]; int a,b;//终点 int dx[]{0,0,1,-1}; int dy[]{1,-1,0,0}; int st[510][510]; void dfs(int x,int y){ for(int i0;i4;i){ int xxdx[i]x; int yydy[i]y; if(xx1||yy1||xxn||yym) continue; if(mg[xx][yy]x) continue; if(st[xx][yy]) continue; if(xxayyb) {ans; return;} st[xx][yy]1; dfs(xx,yy); st[xx][yy]0; } } int main(){ int t; cint; while(t--){ memset(st,0,sizeof(st)); ans0; cinnm; int x,y; for(int i1;in;i){ for(int j1;jm;j){ cinmg[i][j]; if(mg[i][j]s) { xi,yj;} if(mg[i][j]t) { ai,bj;} } } dfs(x,y); if(ans) coutYESendl; else coutNOendl; } return 0 ; }
想法
今天看网课讲到bfs的时间复杂度要比dfs小其实是回溯了的dfs时间复杂度才比bfs大很多所以就试试bfs的写法,过了。还学到了一个小技巧队列中的坐标的存储可以不用数对pair用一个数值表示。 代码
#includebits/stdc.h using namespace std; int n,m; int ans; char mg[510][510]; int dx[]{0,0,1,-1}; int dy[]{1,-1,0,0}; int st[510][510]; queue int q; void bfs(int x,int y){ q.push(x*my); while(!q.empty()){ int aq.front()/m; int bq.front()%m; q.pop(); for(int i0;i4;i){ int xxadx[i]; int yybdy[i]; if(mg[xx][yy]x) continue; if(mg[xx][yy]t) { ans1;break;}//到终点 if(st[xx][yy]) continue; if(xxn||xx0||yy0||yym) continue; st[xx][yy]1; q.push(xx*myy); } if(ans1) return ; } } int main(){ int t; cint; while(t--){ memset(st,0,sizeof(st)); ans0; cinnm; int x,y; for(int i0;in;i){ for(int j0;jm;j){ cinmg[i][j]; if(mg[i][j]s) { xi,yj;} } } st[x][y]1; bfs(x,y); if(ans) coutYESendl; else coutNOendl; } return 0 ; }
事情到这并没有结束我写完就去翻了一下别人的题解发现其实也可以用dfs写出来我们不需要具体路径只需要知道起点终点是否连通我本来想用连通块写的但感觉还是会超时就否决了因此本题不用回溯也不可以回溯回溯会超时。这么做时间复杂度和上一个bfs的时一样的就是全部格子都搜了一遍时间复杂度为On*m。
代码
#includebits/stdc.h using namespace std; int n,m; int ans; char mg[510][510]; int a,b;//终点 int dx[]{0,0,1,-1}; int dy[]{1,-1,0,0}; int st[510][510]; void dfs(int x,int y){ for(int i0;i4;i){ int xxdx[i]x; int yydy[i]y; if(xx1||yy1||xxn||yym) continue; if(mg[xx][yy]x) continue; if(st[xx][yy]) continue; if(xxayyb) {ans; return;} st[xx][yy]1; dfs(xx,yy); //st[xx][yy]0; } } int main(){ int t; cint; while(t--){ memset(st,0,sizeof(st)); ans0; cinnm; int x,y; for(int i1;in;i){ for(int j1;jm;j){ cinmg[i][j]; if(mg[i][j]s) { xi,yj;} if(mg[i][j]t) { ai,bj;} } } dfs(x,y); if(ans) coutYESendl; else coutNOendl; } return 0 ; }
嗐其实还是感觉怪怪的再想想吧。
