首页 > 代码库 > UVA 11624 UVA 10047 两道用 BFS进行最短路搜索的题
UVA 11624 UVA 10047 两道用 BFS进行最短路搜索的题
很少用bfs进行最短路搜索,实际BFS有时候挺方便得,省去了建图以及复杂度也降低了O(N*M);
UVA 11624 写的比较挫
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; struct node{ int ft; int sta; }flo[1010][1010]; int vis[1010][1010]; struct person{ int x,y,t,fx,fy; }; int R,C; int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}}; typedef pair<int,int> pill; queue<pill> v; queue<person> q; void init() { memset(vis,0,sizeof vis); while (!v.empty()){ pill x=v.front(); v.pop(); for (int i=0;i<4;i++){ int nx=x.first+dir[i][0]; int ny=x.second+dir[i][1]; int tmp=flo[x.first][x.second].ft+1;; if (nx<0 || ny<0 || nx>=R || ny>=C) continue; if (flo[nx][ny].ft>=0 && flo[nx][ny].ft<=tmp || flo[nx][ny].sta==0) continue; flo[nx][ny].ft=flo[x.first][x.second].ft+1; pill b=make_pair(nx,ny); if (!vis[nx][ny]) v.push(b); vis[nx][ny]=1; } } } int bfs(person x) { memset(vis,0,sizeof vis); while (!q.empty()) q.pop(); q.push(x); int s=1<<30; while (!q.empty()){ person u=q.front(); q.pop(); if (u.t>=s) continue; if (u.x==0 || u.y==0 || u.x==R-1 || u.y==C-1) {s=u.t;break;} for (int i=0;i<4;i++){ int xx=u.x+dir[i][0]; int yy=u.y+dir[i][1]; if (xx<0 || yy<0 || xx>=R || yy>=C) continue; if (xx==u.fx && yy==u.fy) continue; if (flo[xx][yy].sta!=1 || flo[xx][yy].ft>=0 && flo[xx][yy].ft<=u.t+1) continue; person b=(person){xx,yy,u.t+1,u.x,u.y}; if (!vis[xx][yy]) q.push(b); vis[xx][yy]=1; } } return s; } int main() { int t,sx,sy;char ch; scanf("%d",&t); while (t--){ while (!v.empty()) v.pop(); scanf("%d%d",&R,&C); getchar(); for (int i=0;i<R;i++){ for (int j=0;j<C;j++){ scanf("%c",&ch); //cout<<ch<<endl; if (ch==‘.‘) {flo[i][j].sta=1;flo[i][j].ft=-1;} else if (ch==‘#‘){flo[i][j].sta=0;flo[i][j].ft=-1;} else if (ch==‘F‘){ flo[i][j].sta=flo[i][j].ft=0; pill a;a.first=i;a.second=j;v.push(a); } else if (ch==‘J‘) sx=i,sy=j; } getchar(); } init(); person a=(person){sx,sy,0,-1,-1}; int ans=bfs(a); if (ans<(1<<30)) printf("%d\n",ans+1); else puts("IMPOSSIBLE"); } return 0; }
UVA 10047
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; int R,C; int vis[30][30][5][5]; int mat[30][30]; int sx,sy,ex,ey; int dir[][2]={{-1,0},{0,1},{1,0},{0,-1}}; struct t1{ int x,y,d,c,t; }; int bfs(t1 a) { queue<t1> q; q.push(a); memset(vis,0,sizeof vis); while (!q.empty()){ t1 u=q.front(); q.pop(); if (u.x==ex && u.y==ey && u.c==0){ //cout<<" pass "<<u.x<<" "<<u.y<<endl; return u.t; } vis[u.x][u.y][u.d][u.c]=1; int nd=u.d+1; if (nd>3) nd=0; t1 nx=u; nx.d=nd; nx.t=u.t+1; if (!vis[nx.x][nx.y][nx.d][nx.c]) q.push(nx); vis[nx.x][nx.y][nx.d][nx.c]=1; nd=u.d-1; if (nd<0) nd=3; nx=u; nx.d=nd; nx.t=u.t+1; if (!vis[nx.x][nx.y][nx.d][nx.c]) q.push(nx); vis[nx.x][nx.y][nx.d][nx.c]=1; int xx=u.x+dir[u.d][0]; int yy=u.y+dir[u.d][1]; if (xx<0 || yy<0 || xx>=R || yy>=C) continue; if (mat[xx][yy]==0) continue; int nc=u.c+1; if (nc>4) nc=0; t1 b=(t1){xx,yy,u.d,nc,u.t+1}; if (!vis[b.x][b.y][b.d][b.c]) q.push(b); vis[b.x][b.y][b.d][b.c]=1; } return -1; } int main() { char ch; int kase=0; while (scanf("%d%d",&R,&C)){ if (R==0) break; getchar(); memset(mat,0,sizeof mat); for (int i=0;i<R;i++){ for (int j=0;j<C;j++){ ch=getchar(); if (ch!=‘#‘) mat[i][j]=1; if (ch==‘S‘) sx=i,sy=j; if (ch==‘T‘) ex=i,ey=j; } getchar(); } //cout<<ex<<" exy "<<ey<<endl; t1 a=(t1){sx,sy,0,0,0}; int ans=bfs(a); if (kase) puts(""); printf("Case #%d\n",++kase); if (ans==-1)puts("destination not reachable"); else printf("minimum time = %d sec\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。