基础bfs题目的变形，在结构体里设定答案，在状态更新后才进行判断。两个基础的bfs.
#include <iostream> #include <cstring> #include <queue> using namespace std; int const maxn = 2000; int vis[maxn][maxn]; int rr,cc; char map[maxn][maxn]; int er,ec; int dr[] ={0,-1,0,1}; int dc[]= {1,0,-1,0}; struct point { int r,c; int val; point(int _r=0,int _c=0,int _val=0):r(_r),c(_c),val(_val){} bool operator== (const point& tmp) { return r==tmp.r&&c==tmp.c; } bool isle() { return r>=1&&r<=rr&&c<=cc&&c>=1; } bool isvis() { return vis[r][c]; } bool isgo() { if(map[r][c]=='.') return 1; else return 0; } bool isde() { return r==er&&c==ec; } }; queue<point> D; queue<point> P; int bfs() { int k; while (!P.empty()) { if(!D.empty()) k=D.front().val; while(!D.empty()&&D.front().val==k) { for (int i=0;i<4;i++) { point pp(D.front().r+dr[i],D.front().c+dc[i],D.front().val+1); if(pp.isle()&&!pp.isde()&&pp.isgo()) { map[pp.r][pp.c] = 'X'; D.push(pp); } } D.pop(); } if (!P.empty()) k=P.front().val; while (!P.empty()&&P.front().val==k) { for(int i=0;i<4;i++) { point pp(P.front().r+dr[i],P.front().c+dc[i],P.front().val+1); if(pp.isde()) return pp.val; if (pp.isle()&&!pp.isvis()&&pp.isgo()) { vis[pp.r][pp.c] = 1; P.push(pp); } } P.pop(); } } return 0; } int main() { while(cin>>rr>>cc&&rr){ while (!D.empty()) D.pop(); while (!P.empty()) P.pop(); memset(vis,0,sizeof(vis)); for (int i=1;i<=rr;i++) for (int j=1;j<=cc;j++) { cin>>map[i][j]; if(map[i][j]=='D') { map[i][j]='X'; D.push(point(i,j,0)); } if(map[i][j]=='P') { map[i][j]='.'; vis[i][j]=1; P.push(point(i,j,0)); } if(map[i][j]=='E') { er=i;ec=j; map[i][j]='.'; } } int ans = bfs(); if (ans) cout<<ans<<endl; else cout<<"YYR is extremely dangerous!"<<endl; } }这个代码还没过，不知道哪里错了，以后再修正。
#include <iostream> #include <string.h> #include <queue> #include <stack> #include <vector> using namespace std; int r,c; const int maxn = 2000; int map[maxn][maxn]; int vis[maxn][maxn]; int dr[] ={0,-1,0,1}; int dc[]= {1,0,-1,0}; struct point { int r; int c; point(int a=0,int b=0):r(a),c(b){} bool operator==(const point& tmp) { return r==tmp.r&&c==tmp.c; } }E; queue<point> Q1; queue<point> D; void bfs_d() { stack<point> s; while (!D.empty()) { s.push(D.front()); D.pop(); } while(!s.empty()) { for (int i=0;i<4;i++) { int nr=s.top().r+dr[i]; int nc=s.top().c+dc[i]; if(nr>=1&&nr<=r&&nc>=1&&nc<=c) { if(map[nr][nc]&&!(nr==E.r&&nc==E.c)) { map[nr][nc]=0; D.push(point(nr,nc)); } } } s.pop(); } } int bfs_p() { stack<point> s; if(Q1.empty()) return -1; while(!Q1.empty()) { s.push(Q1.front()); Q1.pop(); } while(!s.empty()) { for(int i=0;i<4;i++) { int nr=s.top().r+dr[i]; int nc=s.top().c+dc[i]; if(nr==E.r&&nc==E.c) return 1; if(nr>=1&&nr<=r&&nc>=1&&nc<=c) { if(map[nr][nc]&&!vis[nr][nc]) { Q1.push(point(nr,nc)); vis[nr][nc]=1; } } } s.pop(); } } int bfs() { int k=1; if (D.front()==E) return 0; while (1) { bfs_d(); int t = bfs_p(); if(t==-1) return -1; if(t==1) return k; k++; } } int main() { while(cin>>r>>c&&r) { memset(vis,0,sizeof(vis)); while(!Q1.empty()) Q1.pop(); while(!D.empty()) D.pop(); for (int i=1;i<=r;i++) for (int j=1;j<=c;j++) { char ch; cin>>ch; if(ch=='X') map[i][j]=0; if(ch=='.') map[i][j]=1; if(ch=='D') { D.push(point(i,j)); map[i][j]=0;} if(ch=='E') { E.r=i; E.c=j; map[i][j]=1; } if(ch=='P') { Q1.push(point(i,j));map[i][j]=1;vis[i][j]=1;} } int ans = bfs(); if(ans!=-1) cout<<ans<<endl; else cout<<"YYR is extremely dangerous!"<<endl; } }