欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

胜利大逃亡(续) hdu-1429 (bfs状态压缩)

程序员文章站 2024-03-23 22:58:22
...

题目链接:胜利大逃亡(续)


题解:

    整体思路

        找到钥匙后就存起来,找到门时判断当前所需钥匙是否已经找到,若找到,当前门可走,否则,不可走。直到找到出口为止。

    具体思路

        用二进制来存钥匙,比如说:111,代表1、2、3钥匙都找到了,而100表示只有3钥匙。那应该如何储存呢。当找到x钥匙时,用sta表示当前状态,则sta=1<< (x-1),也就是将1在二进制中左移(x-1)位。state表示当前储存钥匙的状态,state=state|sta,将钥匙存到状态中 ;

        当找到门时,用sta表示当前门所需要钥匙的状态,然后判断(sta&state)是否为0,若为0则说明当前门没有钥匙,否则则有。

        此题的的标记数组也需要钥匙的状态来判定是否标记。当再次经过x,y时,若此时的钥匙状态和上次经过时的钥匙状态相比没有改变,则此时不能重复走此点。

代码:

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
char Map[22][22];///地图;
int c[4][2]= {1,0,0,1,0,-1,-1,0};///方向数组;
int vis[22][22][10100]= {0};///标记数组;
int n,m,t;

struct yun
{
    int x,y,s;
    int state;
};

int bfs(int x,int y)
{
    queue<yun> Q;
    yun st,en;
    st.x=x;
    st.y=y;
    st.state=0;
    st.s=0;
    vis[x][y][0]=1;
    Q.push(st);
    while(Q.size())
    {
        st=Q.front();
        Q.pop();
        for(int i=0; i<4; i++)
        {
            int dx=st.x+c[i][0];
            int dy=st.y+c[i][1];
            if(dx<0||dy<0||dx>=n||dy>=m||Map[dx][dy]=='*')
                continue;
            en.state=st.state;
            if(Map[dx][dy]>='a'&&Map[dx][dy]<='j')///找到钥匙;
            {
                int sta=1;
                sta=sta<<(Map[dx][dy]-'a');
                en.state=st.state|sta;///存入状态;
            }
            if(Map[dx][dy]>='A'&&Map[dx][dy]<='J')///找到门;
            {
                int sta=1;
                sta=sta<<(Map[dx][dy]-'A');
                if((st.state&sta)==0)///(括号别忘带)判断是否有钥匙;
                    continue;
            }
            if(Map[dx][dy]=='^'&&st.s+1<t)///找到出口;
                return st.s+1;
            if(vis[dx][dy][en.state])///再次访问此状态;
                continue;
            vis[dx][dy][en.state]=1;
            en.x=dx;
            en.y=dy;
            en.s=st.s+1;
            Q.push(en);
        }
    }
    return -1;
}

int main()
{
    int i,j,s_x,s_y;
    while(~scanf("%d%d%d",&n,&m,&t))
    {
        memset(vis,0,sizeof(vis));
        for(i=0; i<n; i++)
        {
            scanf("%s",Map[i]);
            for(j=0; j<m; j++)
            {
                if(Map[i][j]=='@')
                {
                    s_x=i;
                    s_y=j;
                }
            }
        }
        int ans=bfs(s_x,s_y);
        printf("%d\n",ans);
    }

}

相关标签: 状态压缩