01迷宫
2022/4/20 23:20:27
本文主要是介绍01迷宫,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这个题本质上是flood fill 变形+记忆化搜索 有m个读入数据,每次bfs或者dfs必然会超时 就把之前已经搜过的点标记一下,然后这个算是01相邻的一个连通块,这个实质上就是求哪一块01连通块里面元素的个数 bfs#include<iostream> #include<cstring> #include<queue> using namespace std; typedef pair<int,int> PAII; int n,m; const int N=1010,M=1e6+10; char ch[N][N]; int f[N][N],cnt[M]; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int bfs(int x,int y,int u) { queue<PAII> q; q.push({x,y}); cnt[u]=1; f[x][y]=u;//看看是第几层 while(q.size()) { auto t=q.front(); q.pop(); int a=t.first,b=t.second; for(int i=0;i<4;i++) { int xx=a+dx[i],yy=b+dy[i]; if(xx<0||yy<0||xx>=n||yy>=n) continue; if(ch[a][b]-'0'==!(ch[xx][yy]-'0')&&f[xx][yy]==-1) { q.push({xx,yy}); cnt[u]++; f[xx][yy]=u; } } } return cnt[u]; } int main(){ cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>ch[i][j]; memset(f,-1,sizeof(f)); for(int i=0;i<m;i++) { int a,b; cin>>a>>b; a--; b--; if(f[a][b]==-1) { int t=bfs(a,b,i); //cout<<t<<endl; cnt[i]=t; } else cnt[i]=cnt[f[a][b]]; } for(int i=0;i<m;i++) cout<<cnt[i]<<endl; return 0; }
Copy
dfs
#include<iostream> #include<cstring> using namespace std; const int N=5050; int res[100000],f[N][N];//答案和标记 char ch[N][N]; int n,m; void dfs(int r,int c,int z,int l) { if(r<0||c<0||r>=n||c>=n||f[r][c]!=-1||ch[r][c]-'0'!=z) return ; f[r][c]=l;// res[l]++; dfs(r-1,c,!z,l); dfs(r+1,c,!z,l); dfs(r,c-1,!z,l); dfs(r,c+1,!z,l); } int main(){ cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>ch[i][j]; memset(f,-1,sizeof(f)); for(int i=0;i<m;i++) { int a,b; cin>>a>>b; a--; b--; if(f[a][b]==-1) dfs(a,b,ch[a][b]-'0',i); else res[i]=res[f[a][b]]; } for(int i=0;i<m;i++) cout<<res[i]<<endl; return 0; } /* 确实可以用dfs,但如果每一次输入都来一次dfs,那必定超时 所以考虑把每一个点的答案都记录下来,如果没被记录就来一次dfs,可以就直接用 */
这篇关于01迷宫的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行