noi--1159:Maze(bfs)_综合

1159:Maze

描述

Acm, a treasure-explorer, is exploring again. This time he is in a special maze, in which there are some doors (at most 5 doors, represented by ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ respectively). In order to find the treasure, Acm may need to open doors. However, to open a door he needs to find all the door’s keys (at least one) in the maze first. For example, if there are 3 keys of Door A, to open the door he should find all the 3 keys first (that’s three ‘a’s which denote the keys of ‘A’ in the maze). Now make a program to tell Acm whether he can find the treasure or not. Notice that Acm can only go up, down, left and right in the maze.

输入

The input consists of multiple test cases. The first line of each test case contains two integers M and N (1 < N, M < 20), which denote the size of the maze. The next M lines give the maze layout, with each line containing N characters. A character is one of the following: ‘X’ (a block of wall, which the explorer cannot enter), ‘.’ (an empty block), ‘S’ (the start point of Acm), ‘G’ (the position of treasure), ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ (the doors), ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ (the keys of the doors). The input is terminated with two 0’s. This test case should not be processed.

输出

For each test case, in one line output “YES” if Acm can find the treasure, or “NO” otherwise.

样例输入

4 4  

S.X.  

a.X.  

..XG  

....  

3 4  

S.Xa  

.aXB  

b.AG  

0 0

样例输出

YES  

NO

题意：从S走到G，中间X是墙，‘.’是路，A-E是门，a-e是门的钥匙，要想进入门必须要找到所有的钥匙。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<stdlib.h>
using namespace std;
int  w[4][2]={
   {
   0,1},{
   1,0},{-1,0},{
   0,-1}};
char  map[23][23];
int  v[23][23];
int n,m;
struct zz           //记录搜索坐标 
{int x;      int y;}xs,ls;
struct md
{int x;   // x,y记录门的坐标 int y;int v;      //标记钥匙是否收集齐 int v1;     //标记是否能到门 int g;      //该门钥匙总数 int z;      //收集到该门钥匙数 
}door[8];
void  bfs(int x,int y)          //bfs 
{queue<zz>q;xs.x=x;xs.y=y;v[x][y]=1;q.push(xs);while(!q.empty()){xs=q.front();q.pop();for(int i=0;i<4;i++){int xx=xs.x+w[i][0];int yy=xs.y+w[i][1];if(xx<n&&xx>=0&&yy>=0&&yy<m&&v[xx][yy]!=1&&map[xx][yy]!='X'){if(map[xx][yy]<='e'&&map[xx][yy]>='a'){ls.x=xx;ls.y=yy;v[xx][yy]=1; q.push(ls);door[map[xx][yy]-'a'].z++;if(door[map[xx][yy]-'a'].g==door[map[xx][yy]-'a'].z) //钥匙集齐 {door[map[xx][yy]-'a'].v1=1;                     //标记钥匙收集齐 if(door[map[xx][yy]-'a'].v==1)                  //判断是否能走到门 {       ls.x=door[map[xx][yy]-'a'].x;ls.y=door[map[xx][yy]-'a'].y;v[ls.x][ls.y]=1;                        q.push(ls);}}}       else if(map[xx][yy]>='A'&&map[xx][yy]<='E')         //走到门 {door[map[xx][yy]-'A'].v=1;                  //标记走到了门 if(door[map[xx][yy]-'A'].v1==1)             //判断是否收集齐了钥匙 {ls.x=xx;ls.y=yy;v[xx][yy]=1; q.push(ls);}}else    if(map[xx][yy]=='.'){   ls.x=xx;ls.y=yy;v[xx][yy]=1; q.push(ls);}else    if(map[xx][yy]=='G')            //出去条件 {printf("YES\n");return ;}}}}printf("NO\n");}int main ()
{while(scanf("%d%d",&n,&m),n!=0||m!=0){    int xx,yy;memset(v,0,sizeof(v));memset(map,0,sizeof(map));for(int i=0;i<8;i++){   door[i].v1=0;door[i].v=0;door[i].z=0;                                        //初始化 door[i].g=0;}for(int i=0;i<n;i++){   scanf("%s",&map[i]);for(int j=0;j<m;j++){   if(map[i][j]<='e'&&map[i][j]>='a'){door[map[i][j]-'a'].g++;                    //记录钥匙有几个才能打开门 }else if(map[i][j]=='S'){xx=i;                                       //记录起点 yy=j;}else if(map[i][j]<='E'&&map[i][j]>='A'){door[map[i][j]-'A'].x=i;door[map[i][j]-'A'].y=j;                        //记录门所在位置 }}}getchar();bfs(xx,yy);}return 0; 
}