nyoj 82 迷宫寻宝（一）

亦凉 2022-08-09 15:36 162阅读 0赞

/**
     时间限制：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
    */

/** 要点： 一个门必须要找全所有这个门的钥匙才能将其打开，门最多有5扇，在数据输入时统计其对应钥匙的个数，然后从起始点搜索 注意钥匙也是可以到达的地方， 要解决的关键问题：门与钥匙的问题！能否找到对应门的所有钥匙！！ 对应的解决方案：在搜索过程中每遇到一个门检测是否已找全其所有对应的钥匙，找全了就直接开门，进入下 一个状态；找不全，由于不确定是否后续可以找到所有的钥匙，需要把该门先存起来（用一个栈） 在搜索过程中每遇到一个钥匙，由于钥匙的地方是可以到达的，直接进入该地点，同时检测是否已经找全了其对应 的全部门的所有钥匙，一旦发现找全了，则说明其对应的所有该类门都可以打开进入了，于是将栈中存储该类的门 全部导入到队列中去。 数据结构 + 算法 = 程序 */
    
    #include <iostream>
    #include <map>
    #include <queue>
    #include <cstdio>
    #include <memory.h>
    #include <ctime>
    #define S 30
    using namespace std;
    
    typedef pair<int,int>point;
    queue<point>que;
    
    int N,M,sx,sy;
    char maze[S][S];
    int vis[S][S],key[5];
    const int dirx[4]={-1,1,0,0},diry[4]={
       0,0,-1,1};
    vector<point>door[5];
    
    bool bfs(){
        point cur,next;
        int acquire[5]={
       0};
        while(que.size()){
            cur = que.front();
            que.pop();
            int cx = cur.first,cy = cur.second;
            //cout << "step:" << cx << "," << cy << "value:" << maze[cx][cy] << endl;
            //if(maze[cx][cy]=='G') return true;
            for(int i=0;i<4;i++){
                int nx = cx+dirx[i] , ny = cy+diry[i];
                char ch = maze[nx][ny];//ch是下一个能到达的位置的状态
                if(nx>=0&&nx<N&&ny>=0&&ny<M&&ch!='X'&&!vis[nx][ny]){
       //先看能不能走，之前是否走过
                    if(ch=='.'){
                        vis[nx][ny] = 1;
                        que.push(make_pair(nx,ny));
                    }
                    else if(ch>='a'&&ch<='e'){
       //找到对应门的钥匙，判断对应的门能否打开
                        vis[nx][ny] = 1;
                        //maze[nx][ny] = '.';
                        acquire[ch-'a']++;
                        que.push(make_pair(nx,ny));
                        //一旦能开，将对应的所有门打开（即导入到队列中去）
                        while(key[ch-'a']==acquire[ch-'a']&&!door[ch-'a'].empty()){
                            que.push(door[ch-'a'].back());
                            door[ch-'a'].pop_back();
                        }
                    }
                    else if(ch>='A'&&ch<='E'){
                        int t = ch-'A';
    //必须要在这儿push而不能在main函数数据输入时push门的坐标，因为后期如果门所有的钥匙都找到了的话并不是
    //所有的门都可以开，因为有的门是无法到达的，被墙壁阻隔！！
                        if(acquire[t]!=key[t]){
       //开不了门，将门的坐标存入一个栈，看后面能不能开，如果能开就再将其导入队列中（队列中的元素都是可以到达的）
                            door[t].push_back(make_pair(nx,ny));
                            vis[nx][ny] = 1;    
                        }
                        else{
       //能开门，直接开，并将位置坐标导入到队列中去
                            vis[nx][ny] = 1;
                            que.push(make_pair(nx,ny));
                        }
                    }
                    else if(ch=='G') return true;
                }
            }
        }
        return false;
    }
    
    int main(){
        while(scanf("%d %d",&N,&M)&&(N||M)){
            getchar();
            memset(key,0,sizeof(key));
            memset(vis,0,sizeof(vis));
            memset(door,0,sizeof(door));
            while(que.size()) que.pop();
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    scanf("%c",&maze[i][j]);
                    if(maze[i][j]=='S'){
                        sx = i;
                        sy = j;
                    }//key[]事先存好了所有对应的钥匙种类对应数目
                    else if(maze[i][j]>='a'&&maze[i][j]<='e'){
                        int t = maze[i][j] - 'a';
                        key[t]++;
                    }
                }
                getchar();
            }
            vis[sx][sy] = 1;
            que.push(make_pair(sx,sy));
            if(bfs()) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }