Key Task

The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 ≤ R, C ≤ 100) specifying the map size. Then there are R lines each containing C characters. Each character is one of the following:



Note that it is allowed to have

more than one exit,

no exit at all,

more doors and/or keys of the same color, and

keys without corresponding doors and vice versa.

You may assume that the marker of your position (“*”) will appear exactly once in every map.

There is one blank line after each map. The input is terminated by two zeros in place of the map size.

1 10
*........X

1 3
*#X

3 20
####################
#XY.gBr.*.Rb.G.GG.y#
####################

0 0

Escape possible in 9 steps.
The poor student is trapped!
Escape possible in 45 steps.

每个格子都有不同的状态，关键是在判断在走到当前格子的当前key状态是否走过。

#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
using namespace std;
#define N 105
struct locate
{
    int x,y,step,state;
};
char map[N][N];
int state[N][N][16],n,m;

int BFS(int sx,int sy)
{
    queue<locate>q;
    locate p,tp;
    int dir[4][2]={0,1,1,0,0,-1,-1,0};
    char door[6]={"BYRG"},key[6]={"byrg"};

    memset(state,0,sizeof(state));
    p.step=0; p.state=0;
    p.x=sx; p.y=sy;
    q.push(p); state[sx][sy][0]=1;

    while(!q.empty())
    {
        p=q.front(); q.pop();
        for(int e = 0;e < 4;++e)
        {
            tp.x=p.x+dir[e][0];
            tp.y=p.y+dir[e][1];

            if(tp.x>=0&&tp.x<n&&tp.y>=0&&tp.y<m&&map[tp.x][tp.y]!='#'&&!state[tp.x][tp.y][p.state])
            {
                tp.step=p.step+1;
                tp.state=p.state;
                if(map[tp.x][tp.y]=='X')
                    return tp.step;
                int flag=0;
                for(int i=0;i<4;i++)
                    if(map[tp.x][tp.y]==key[i])
                    {
                        flag=1; tp.state|=(1<<i);break;
                    }
                state[tp.x][tp.y][tp.state]=1;
                if(!flag)
                {
                    flag=0;
                    for(int i=0;i<4;i++)
                        if(map[tp.x][tp.y]==door[i])
                        {
                            flag=1;
                            if(tp.state&(1<<i))
                                flag=2;
                            break;
                        }
                    if(flag!=1)
                        q.push(tp);
                }
                else
                    q.push(tp);
            }
        }
    }
    return 0;
}

int main()
{
    int sx,sy;
    while(scanf("%d%d",&n,&m)>0)
    {
        if(n==0&&m==0)
            break;
        for(int i=0;i<n;i++)
            scanf("%s",map[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            if(map[i][j]=='*')
            sx=i,sy=j;
        int ans=BFS(sx,sy);
        if(ans)
            printf("Escape possible in %d steps.\n",ans);
        else
            printf("The poor student is trapped!\n");
    }
}

1885Key Task（BFS+状态压缩）（胜利大逃亡续）一个意思

原文：http://blog.csdn.net/u010372095/article/details/41523199