首页 > 代码库 > ny82 迷宫寻宝(一) map+queue

ny82 迷宫寻宝(一) map+queue

题目地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=82

AC代码:讲解,先统计在可搜索范围内对应的钥匙数,把搜到的门存到另外的一个队列中,第一个搜索结束后,开始看搜到的钥匙能否打看门,

            如果能打看门,存到第一个队列中,在进行搜寻,知道找到宝藏,或者什么也没有找到,则退出;

AC代码:

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<map>
 6 #include<queue>
 7 using namespace std;
 8 map<char,int >key;
 9 map<char,int >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 T
15 {
16     int x,y;
17 }now,eed;
18 struct KEY
19 {
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"<<endl;
90             else cout<<"NO"<<endl;
91     }
92     return 0;
93 //3 4
94 //S.XX
95 //.aXB
96 //b.AG
97 }