hdu 1429 bfs+二进制状态压缩

开始时候只用了BFS，显然超时啊，必然在结构体里加一个数组什么的判重啊，开始用的一个BOOL数组，显然还是不行，复杂度高，每次都要遍历数组来判重；后百度之，学习了二进制状态压缩，其实就用一个二进制数来表示当前状态，然后就可以用简单快速位运算来操作了。

#include<map>

#include<iostream>

#include<queue>

#include<cstring>

#include<cstdio>

using namespace std;

char a[30][30];

int mark[30][30][1025];       //判重，坐标+钥匙数，二进制表示，每位代表不同钥匙，1有，0无。

int minn=99999;

int f[4][2]={0,1,0,-1,1,0,-1,0};

struct xy

{

    int x,y;

    int count;               // 已经走的步数

    int key;                  //  对应一个二进制数，如0001，在第一位有一把钥匙。

};

void bfs(xy from,int t,int n,int m)

{

    queue<xy>q;

    q.push(from);

    while(!q.empty())

    {

        xy cur=q.front();

        q.pop();

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

        {

            xy next(cur);

            next.x+=f[i][0];

            next.y+=f[i][1];

            if(next.x>=0&&next.y>=0&&next.x<n&&next.y<m&&a[next.x][next.y]!='*'&&mark[next.x][next.y][next.key]==0)

            {

                if(a[next.x][next.y]>='A'&&a[next.x][next.y]<='J')

                  {

                      if((next.key&(1<<(a[next.x][next.y]-'A')))==0)continue; //&的优先级比==低！！按位与来判断有无我这把钥匙

                  }

               next.count++;

               if(a[next.x][next.y]>='a'&&a[next.x][next.y]<='j')

               {

                   next.key=next.key|(1<<(a[next.x][next.y]-'a'));     //按位或来添加这把钥匙。

               }

                if(next.count==t){return;}

                if(a[next.x][next.y]=='^'){minn=next.count;return;}

                q.push(next);

             mark[next.x][next.y][next.key]=1;

            }

        }

    }

    return;

}

int main()

{

    int n,m,t;

    while(cin>>n>>m>>t)

    {

        xy from;

        minn=99999;

        memset(mark,0,sizeof(mark));

        from.count=0;

        from.key=0;

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

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

        {

            cin>>a[i][j];

            if(a[i][j]=='@'){from.x=i;from.y=j;}

        }

        bfs(from,t,n,m);

        if(minn==99999)cout<<-1<<endl;

        else cout<<minn<<endl;

        cout<<endl;

    }

}

巴特西

hdu 1429 bfs+二进制状态压缩

最新文章

热门文章