BFS-修改范例-开门系列-单扇多类门配多钥匙

/* BFS:多类单个门，配多把钥匙 */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> using namespace std; #include<queue> const int INF = 999999; struct node { int x,y; }; struct DOOR { int x,y; int find; }; queue<node> q; int n,m,time; char mp[25][25]; int vis[25][25]; int key[5]; int skey[5]; DOOR door[5]; int xx[4]={1,-1,0,0}; int yy[4]={0,0,1,-1}; int bfs(int x,int y) { while(!q.empty ()) q.pop (); node from,next; int i; from.x=x,from.y=y; vis[x][y]=1; q.push (from); while(!q.empty ()) { from=q.front (); q.pop (); for(i=0;i<4;i++) { int dx=from.x+xx[i]; int dy=from.y+yy[i]; if(dx>=0&&dx<n&&dy>=0&&dy<m&&vis[dx][dy]==0&&mp[dx][dy]!='X') { next.x=dx; next.y=dy; if(mp[dx][dy]=='G') return 1; else if(mp[dx][dy]>='a'&&mp[dx][dy]<='e')//find the key { vis[dx][dy]=1; key[mp[dx][dy]-'a']++; if(key[mp[dx][dy]-'a']==skey[mp[dx][dy]-'a']&&door[mp[dx][dy]-'a'].find==1) { door[mp[dx][dy]-'a'].find=2; node t; t.x=door[mp[dx][dy]-'a'].x; t.y=door[mp[dx][dy]-'a'].y; vis[t.x][t.y]=1; q.push (t); } q.push (next); } else if(mp[dx][dy]>='A'&&mp[dx][dy]<='E')//find the door { door[mp[dx][dy]-'A'].x=dx; door[mp[dx][dy]-'A'].y=dy; door[mp[dx][dy]-'A'].find=1; if(key[mp[dx][dy]-'A']==skey[mp[dx][dy]-'A']&&door[mp[dx][dy]-'A'].find==1) { door[mp[dx][dy]-'A'].find=2; node t; t.x=door[mp[dx][dy]-'A'].x; t.y=door[mp[dx][dy]-'A'].y; vis[t.x][t.y]=1; q.push (t); } } else { vis[dx][dy]=1; q.push (next); } } } } return 0; } int main() { int i,j; int x,y; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); memset(key,0,sizeof(key)); memset(skey,0,sizeof(skey)); memset(door,0,sizeof(door)); for(i=0;i<n;i++) { scanf("%s",mp[i]); for(j=0;j<m;j++) { if(mp[i][j]=='S') x=i,y=j; if(mp[i][j]>='a'&&mp[i][j]<='e') skey[mp[i][j]-'a']++; } } int ans=bfs(x,y); if(ans==1) printf("YES\n"); else printf("NO\n"); } return 0; } /* 4 4 Saaa aaaa XXAX GBbb */

 

转载于:https://www.cnblogs.com/mochenmochen/p/5156907.html