hdu1429（bfs+状态压缩）

思路：有十个门，有十把钥匙，每把钥匙对应一个门，相同的门可以有多个。这样，我们就得按照状态来搜索，用0000000001代表第一个门有钥匙了，1000000000代表第十个门钥匙有了.......一次类推，可以用二进制来表示.......遇到钥匙，可以先拾起这个钥匙，用|；遇到门，可以判断是否有这个门的钥匙,把门状态位移后，&就好........

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

int t[4][2]={1,0,-1,0,0,1,0,-1},vist[25][25][5000];

char str[25][25];

int n,m,tj,flag=0,ans=0;

int qx,qy,zx,zy;

struct node

{

    int x,y;

    int time;

    int k;

};

void bfs()

{

    queue<node>q;

    node p;

    p.x=qx;

    p.y=qy;

    p.time=0;

    p.k=0;

    q.push(p);

    while(!q.empty())

    {

        node p1;

        p1=q.front();

        q.pop();

        if(p1.time>=tj)

        return;

        if(p1.x==zx&&p1.y==zy)

        {

            flag=1;

            ans=p1.time;

            break;

        }

        for(int i=0;i<4;i++)

        {

            node p2;

            p2.x=p1.x+t[i][0];

            p2.y=p1.y+t[i][1];

            p2.time=p1.time+1;

            p2.k=p1.k;

            if(p2.x>=0&&p2.x<n&&p2.y>=0&&p2.y<m&&str[p2.x][p2.y]!='*')

            {

                if('a'<=str[p2.x][p2.y]&&str[p2.x][p2.y]<='z')

                {

                    p2.k=p2.k|(1<<(str[p2.x][p2.y]-'a'));

                    if(!vist[p2.x][p2.y][p2.k])

                    {

                        vist[p2.x][p2.y][p2.k]=1;

                        q.push(p2);

                    }

                }

                else

                if('A'<=str[p2.x][p2.y]&&str[p2.x][p2.y]<='Z')

                {

                     int k=p2.k&(1<<(str[p2.x][p2.y]-'A'));

                    if(!vist[p2.x][p2.y][p2.k]&&k)

                    {

                        vist[p2.x][p2.y][p2.k]=1;

                        q.push(p2);

                    }

                }

                else  if(vist[p2.x][p2.y][p2.k]==0)

                {

                    vist[p2.x][p2.y][p2.k]=1;

                    q.push(p2);

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d%d%d",&n,&m,&tj)>0)

    {

        for(int i=0;i<n;i++)

        scanf("%s",str[i]);

        for(int i=0;i<n;i++)

        for(int j=0;j<m;j++)

        {

            if(str[i][j]=='@')

            {

                qx=i;

                qy=j;

            }

            if(str[i][j]=='^')

            {

                zx=i;

                zy=j;

            }

        }

        flag=0;

        ans=0;

        memset(vist,0,sizeof(vist));

        bfs();

        if(flag==0)

        printf("-1\n");

        else

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

hdu1429（bfs+状态压缩）

最新文章

热门文章