首页 > 代码库 > 迷宫寻宝(一) BFS

迷宫寻宝(一) BFS

迷宫寻宝(一)

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
 
描述

一个叫ACM的寻宝者找到了一个藏宝图,它根据藏宝图找到了一个迷宫,这是一个很特别的迷宫,迷宫里有N个编过号的门(N<=5),它们分别被编号为A,B,C,D,E.为了找到宝藏,ACM必须打开门,但是,开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙(每个门都至少有一把钥匙),例如:现在A门有三把钥匙,ACM就必须找全三把钥匙才能打开A门。现在请你编写一个程序来告诉ACM,他能不能顺利的得到宝藏。

 

 
输入
输入可能会有多组测试数据(不超过10组)。
每组测试数据的第一行包含了两个整数M,N(1<N,M<20),分别代表了迷宫的行和列。接下来的M每行有N个字符,描述了迷宫的布局。其中每个字符的含义如下:
.表示可以走的路
S:表示ACM的出发点
G表示宝藏的位置
X表示这里有墙,ACM无法进入或者穿过。
A,B,C,D,E表示这里是门,a,b,c,d,e表示对应大写字母的门上的钥匙。
注意ACM只能在迷宫里向上下左右四个方向移动。

最后,输入0 0表示输入结束。
输出
每行输出一个YES表示ACM能找到宝藏,输出NO表示ACM找不到宝藏。
样例输入
4 4 
S.X. 
a.X. 
..XG 
.... 
3 4 
S.Xa 
.aXB 
b.AG 
0 0
样例输出
YES 
NO
来源
POJ月赛改编
这个题做了挺长时间:
注意:
1.门可能有多个
2.在搜索的时候用been标记这个门是不是可以到达,用num==key&&key>0表示当前有足够的钥匙可以通过
3.读入的时候有多余空格,不要单个字符读入
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN  22
#define LLL 1000000000
#define INF 1000000009
#define eps 0.00000001
/*
BFS 搜索,在读入图的时候记录abcde所需要的钥匙个数
先BFS一遍,找到所有能找到的钥匙。
然后对于所有的门,如果第一次搜索能到达而且钥匙足够。
把这个门加入队列再搜
*/
struct node
{
    int x, y;
    node() = default;
    node(int _x,int _y):x(_x),y(_y){}
};
node start,aim;
vector<node> door[5];
int key[5], num[5], n, m;//需要的钥匙个数,n行m列
int x[4] = { 0,0,1,-1 }, y[4] = { 1,-1,0,0 };
bool been[MAXN][MAXN];
char g[MAXN][MAXN];
int check()
{
    for (int i = 0; i < 5; i++)
    {
        if (key[i]>0&&num[i] == key[i])
        {
            for (int j = 0; j < door[i].size(); j++)
            {
                if(been[door[i][j].x][door[i][j].y])
                    return i;
            }
        }
    }
    return -1;
}
bool BFS(node s)
{
    queue<node> q;
    been[s.x][s.y] = true;
    q.push(s);
    while (!q.empty())
    {
        node tmp = q.front();
        q.pop();
        //cout << tmp.x << ‘ ‘ << tmp.y << ‘ ‘<<g[tmp.x][tmp.y] << endl;
        if (tmp.x == aim.x&&tmp.y == aim.y)
            return true;
        if ((g[tmp.x][tmp.y] - A >= 0 && g[tmp.x][tmp.y] - A<5)&&(key[g[tmp.x][tmp.y] - A]==0||num[g[tmp.x][tmp.y] - A] != key[g[tmp.x][tmp.y] - A]))
            continue;
        for (int i = 0; i < 4; i++)
        {
            int tx = tmp.x + x[i], ty = tmp.y + y[i];
            if (tx >= 0 && tx < n& ty >= 0 && ty <= m&&!been[tx][ty]
                 &&((g[tx][ty]==.||g[tx][ty]==G||g[tx][ty]-A>=0&&g[tx][ty]-A<5)||(g[tx][ty]-a>=0&&g[tx][ty]-a<5)))
            {
                
                if(g[tx][ty] - a >= 0 && g[tx][ty] - a<5)
                    num[g[tx][ty] - a]++;
                been[tx][ty] = true;
                q.push(node(tx, ty));
            }
        }
    }
    return false;
}
int main()
{
    while (scanf("%d%d", &n, &m), n+m)
    {
        bool f = false;
        memset(been, false, sizeof(been));
        memset(num, 0, sizeof(num));
        memset(key, 0, sizeof(key));
        for (int i = 0; i < 5; i++)
        {
            door[i].clear();
        }
        for (int i = 0; i < n; i++)
        {
            scanf("%s", g[i]);
            for (int j = 0; j < m; j++)
            {
                if (g[i][j] - A >= 0 && g[i][j] - A < 5)
                {
                    door[g[i][j] - A].push_back(node(i, j));
                }
                else if (g[i][j] - a >= 0 && g[i][j] - a < 5)
                {
                    key[g[i][j] - a]++;
                }
                else if (g[i][j] == S)
                {
                    start.x = i, start.y = j;
                }
                else if (g[i][j] == G)
                {
                    aim.x = i, aim.y = j;
                }
            }
        }
        if (BFS(start))
        {
            f = true;
            printf("YES\n");
            continue;
        }
        while (1)
        {
            int k = check();
            if (k == -1) break;
            for (int j = 0; j < door[k].size(); j++)
            {
                if (been[door[k][j].x][door[k][j].y])
                {
                    if (BFS(door[k][j]))
                    {
                        f = true;
                        break;
                    }
                    door[k].erase(door[k].begin() + j);
                }
            }
            if (f)
                break;
        }
        if (!f)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

 

迷宫寻宝(一) BFS