学步园

BFS,细节

注意到达一处时，先更新状态，再判mapp。

边界啊~~但是貌似codeblocks可以自动无视越界。。

#include <cstdio>
#include <cstring>
#include <queue>
#include <ctype.h>
using namespace std;
typedef struct point{
    int x,y,key,step;
}point;
int movee [4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
int main()
{
    char laby[105][105];
    int mapp[16][105][105];
    int r,c;
    while(scanf("%d %d",&r,&c)&&(r+c))
    {
        memset(mapp,0,sizeof(mapp));
//map用来排重，即是已走和未走两状态，至于墙或者门的限制，直接用原图即可！
        for(int i=0;i<r;i++)
            scanf("%s",laby[i]);
        point st;
//如果走到一个地方，再往前走将遇到一个门，但没拿相应钥匙，其他的方向又不会立刻走出，
//则这条路是错的。但是这种情况已经包含在同态同位中。
        bool jmp = 0;
        for(int i=0;i<r&&!jmp;i++)
            for(int j=0;j<c;j++)
            {
                if(laby[i][j]=='*')
                {
                    laby[i][j] = '.';//similate
                    st.x = i;
                    st.y = j;
                    st.key = 0;
                    st.step = 0;
                    jmp = 1;
                    break;
                }
            }
        jmp = 0;
        queue <point> q;
        if(!q.empty())  q.pop();
        q.push(st);
        while(!q.empty())
        {
            point p = q.front();
            q.pop();
            mapp[p.key][p.x][p.y] = 1;
            for(int i=0;i<4;i++)
            {
                int tx = p.x + movee[i][0];
                int ty = p.y + movee[i][1];
                if(tx<0||ty<0||tx>=r||ty>=c) continue;//只顾着考虑墙和钥匙的问题，却忽视了基本的边界判断！！！
                if(laby[tx][ty]=='#'||(mapp[p.key][tx][ty]&&(!islower(laby[tx][ty]))))  continue;//不作为就是有作为。。判重
                //如果是钥匙的话那就按照更新后的钥匙状态算！！！
                if(laby[tx][ty]=='.')
                {
                    point tmp = {tx,ty,p.key,p.step+1};
                    q.push(tmp);
                    mapp[tmp.key][tx][ty] = 1;
                }
                else if(laby[tx][ty]=='X')
                {
                    printf("Escape possible in %d steps.\n",p.step+1);
                    jmp = 1;
                    break;
                }
                else if(islower(laby[tx][ty]))
                {
                    int tkey;
                    if(laby[tx][ty]=='b')  tkey = 1;
                    else if(laby[tx][ty]=='y')  tkey = 1 << 1 ;
                    else if(laby[tx][ty]=='r')  tkey = 1 << 2 ;
                    else if(laby[tx][ty]=='g')  tkey = 1 << 3 ;
                    tkey = tkey | p.key;
                    if(mapp[tkey][tx][ty])  continue;
                    point tmp = {tx,ty,tkey,p.step+1};
                    q.push(tmp);
                    mapp[tmp.key][tx][ty] = 1;
                }
                else
                {
                    bool can = 0;
                    if(laby[tx][ty]=='B')   {if(p.key&1) can = 1;}
                    else if(laby[tx][ty]=='Y')  {if(p.key&(1<<1)) can = 1;}
                    else if(laby[tx][ty]=='R')  {if(p.key&(1<<2)) can = 1;}
                    else if(laby[tx][ty]=='G')  {if(p.key&(1<<3)) can = 1;}
                    if(can)
                    {
                        point tmp = {tx,ty,p.key,p.step+1};
                        q.push(tmp);
                        mapp[tmp.key][tx][ty] = 1;
                    }
                }
            }
            if(jmp) break;

        }
        if(!jmp)  printf("The poor student is trapped!\n");
    }
    return 0;
}