本文共 1986 字，大约阅读时间需要 6 分钟。
题目地址：
AC代码：讲解，先统计在可搜索范围内对应的钥匙数，把搜到的门存到另外的一个队列中，第一个搜索结束后，开始看搜到的钥匙能否打看门，
如果能打看门，存到第一个队列中，在进行搜寻，知道找到宝藏，或者什么也没有找到，则退出；
AC代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 map key; 9 map key1;10 int dir[4][2]={ 0,-1,0,1,-1,0,1,0};11 char mapp[21][21];12 int vis[21][21];13 int s1,s2,e1,e2,m,n;14 struct T15 {16 int x,y;17 }now,eed;18 struct KEY19 {20 int x,y;21 }ee,nn;22 int bfs()23 {24 vis[s1][s2]=1;25 queue< T >aa;26 queue< KEY >bb;27 now.x=s1; now.y=s2;28 aa.push(now);29 while(1)30 {31 while(!aa.empty())//搜寻可以搜的地方，搜到门，存到下一个队列中；32 {33 eed=aa.front();34 aa.pop();35 if(eed.x==e1 && eed.y==e2)36 return 1;37 for(int i=0; i<4; i++)38 {39 now.x=eed.x+dir[i][0];now.y=eed.y+dir[i][1];40 if(now.x>0 && now.x<=m && now.y>0 && now.y<=n && mapp[now.x][now.y]!='X' && vis[now.x][now.y]==0)41 {42 if(mapp[now.x][now.y]>='a' && mapp[now.x][now.y]<='e')// 钥匙43 { key1[mapp[now.x][now.y]]++,aa.push(now); }44 else if(mapp[now.x][now.y]=='.' || mapp[now.x][now.y]=='G')45 aa.push(now);46 else if(mapp[now.x][now.y]>='A' && mapp[now.x][now.y]<='E')47 { 48 nn.x=now.x; nn.y=now.y;49 bb.push(nn);50 }51 vis[now.x][now.y]=1;52 }53 }54 }55 int siz=bb.size();56 while(!bb.empty() && siz--)//遍历搜到的门，看能否打开，如果能的话，存到第一个队列中，再次搜索；57 {58 nn=bb.front();59 if(key[mapp[nn.x][nn.y]+32]==key1[mapp[nn.x][nn.y]+32] && key[mapp[nn.x][nn.y]+32]>0)60 { now.x=nn.x;now.y=nn.y;61 aa.push(now);bb.pop();62 }63 else bb.push(nn),bb.pop();64 }65 if(aa.empty())//如果队列1，为空证明，路已经走不下去了，结束搜索；66 return 0;67 }68 return 0;69 }70 int main()71 {72 while(cin>>m>>n && m+n)73 {74 key.clear();key1.clear();75 memset(vis,0,sizeof(vis));76 for(int i=1; i<=m ;i++)77 for(int j=1 ;j<=n; j++)78 {79 cin>>mapp[i][j];80 if(mapp[i][j]=='S')81 s1=i,s2=j;82 else if(mapp[i][j]=='G')83 e1=i,e2=j;84 else if(mapp[i][j]>='a' && mapp[i][j]<='e')//统计总共的钥匙的个数；85 key[mapp[i][j]]++;86 }87 int ans=bfs();88 if(ans==1)89 cout<<"YES"<
转载地址：http://kqowo.baihongyu.com/