首页 > 代码库 > HDU 1312 (BFS搜索模板题)
HDU 1312 (BFS搜索模板题)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1312
题目大意:问迷宫中有多少个点被访问。
解题思路:
DFS肯定能水过去的。这里就拍了一下BFS。
然后发现自己BFS访问标记有问题,导致某些点被重复访问了。
赶紧改了一下。
#include "cstdio"#include "queue"#include "string"#include "cstring"#include "iostream"using namespace std;int n,m,sx,sy,map[25][25],dir[4][2]={-1,0,1,0,0,-1,0,1},cnt;bool vis[25][25];struct status{ int x,y; status(int x,int y):x(x),y(y) {}};void bfs(int x,int y){ queue<status> Q; Q.push(status(sx,sy)); vis[sx][sy]=true; while(!Q.empty()) { cnt++; status t=Q.front();Q.pop(); for(int s=0;s<4;s++) { int X=t.x+dir[s][0],Y=t.y+dir[s][1]; if(vis[X][Y]||X<0||X>n||Y<0||Y>m||!map[X][Y]) continue; vis[X][Y]=true; Q.push(status(X,Y)); } }}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); string tt; while(cin>>m>>n&&n) { cnt=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { cin>>tt; for(int j=0;j<tt.size();j++) { if(tt[j]==‘#‘) map[i][j+1]=0; if(tt[j]==‘.‘) map[i][j+1]=1; if(tt[j]==‘@‘) {map[i][j+1]=2;sx=i;sy=j+1;} } } bfs(sx,sy); cout<<cnt<<endl; }}
1869483 | 2014-10-14 14:49:59 | Accepted | 1312 | 15MS | 292K | 1246 B | C++ | Physcal |
HDU 1312 (BFS搜索模板题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。