Maze(POJ-2157)

题意

迷宫中有若干个门（最多5个门，分别用 'A', 'B', 'C', 'D', 'E' 来表示）。为了找到宝藏，我们需要把门打开，然而打开某个门首先需要在迷宫中找到这个门的所有钥匙，只能往上、下、左、右四个方向走，判断一下能否找到宝藏。

输入

输入包含多组数据。
每组数据的第一行包含两个整数和 ，表示迷宫的大小。接下来的行，每行包含个字符，表示迷宫地图。其中：字符’X’表示墙，不能通过；’.’表示一个可以行走的空格；’S’表示初始出发位置；’G’为宝藏的位置；'A'、'B'、'C'、 'D'、'E'表示门；'a'、'b'、'c'、'd'、'e'表示对应门的钥匙。
输入以0 0结束，这组输入数据不需要处理。

解题思路

多遍BFS，每次遍历当前能到达的所有点后判断能否打开门（所以要把门的位置存到vector里），如果能打开则在进行一次BFS，反之直接结束。
代码很长但是思路不难。

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

char mp[25][25];
int vis[25][25];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int n, m;
int sx, sy, ex, ey;
int a,b,c,e,d;

struct node {
    int x,y;
};

void print() {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cout<<mp[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
int bfs() {
//    print();
    int ta,tb,tc,td,te,flag=0;
    ta=tb=tc=td=te=0;
    memset(vis,0,sizeof(vis));
    queue<node> q;
    node s; s.x=sx; s.y=sy;
    q.push(s);
    vis[sx][sy]=1;
    vector<node> v;

    while(!q.empty()) {
        s=q.front();
        if(s.x==ex && s.y==ey) return 2;
        q.pop();
        for(int i=0;i<4;i++) {
//            cout<<ta<<"-"<<a<<endl;
            int tx=s.x+dx[i];
            int ty=s.y+dy[i];
            if(tx<=0||tx>n||ty<=0||ty>m) continue;
            if(vis[tx][ty]) continue;
            if(mp[tx][ty]=='X') continue;
            if(mp[tx][ty]=='a') ta++;
            if(mp[tx][ty]=='b') tb++;
            if(mp[tx][ty]=='c') tc++;
            if(mp[tx][ty]=='d') td++;
            if(mp[tx][ty]=='e') te++;
            if(mp[tx][ty]=='A')  {node t; t.x=tx; t.y=ty; v.push_back(t); continue;}
            if(mp[tx][ty]=='B')  {node t; t.x=tx; t.y=ty; v.push_back(t); continue;}
            if(mp[tx][ty]=='C')  {node t; t.x=tx; t.y=ty; v.push_back(t); continue;}
            if(mp[tx][ty]=='D')  {node t; t.x=tx; t.y=ty; v.push_back(t); continue;}
            if(mp[tx][ty]=='E')  {node t; t.x=tx; t.y=ty; v.push_back(t); continue;}
            node t; t.x=tx; t.y=ty;
            q.push(t);
            vis[tx][ty]++;
        }
    }
    for(int i=0;i<v.size();i++) {
        if(mp[v[i].x][v[i].y]=='A'&&ta>=a) mp[v[i].x][v[i].y]='.',flag=1;
        if(mp[v[i].x][v[i].y]=='B'&&tb>=b) mp[v[i].x][v[i].y]='.',flag=1;
        if(mp[v[i].x][v[i].y]=='C'&&tc>=c) mp[v[i].x][v[i].y]='.',flag=1;
        if(mp[v[i].x][v[i].y]=='D'&&td>=d) mp[v[i].x][v[i].y]='.',flag=1;
        if(mp[v[i].x][v[i].y]=='E'&&te>=e) mp[v[i].x][v[i].y]='.',flag=1;
    }
    return flag;
}
int main() {
//    freopen("in.txt","r",stdin);
    while(cin>>n>>m&&(n+m)) {
        a=b=c=d=e=0;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                cin>>mp[i][j];
                if(mp[i][j]=='a') a++;
                if(mp[i][j]=='b') b++;
                if(mp[i][j]=='c') c++;
                if(mp[i][j]=='d') d++;
                if(mp[i][j]=='e') e++;
                if(mp[i][j]=='S') sx=i,sy=j;
                if(mp[i][j]=='G') ex=i,ey=j;
            }
        }
        while(1) {
            int ans=bfs();
            if(ans==2) {cout<<"YES"<<endl; break;}
            else if(ans==0) {cout<<"NO"<<endl; break;}
        } 
    }
}