hdu 1429 bfs+二进制状态压缩

雨点打透心脏的1/2处 2021-12-20 06:03 210阅读 0赞

开始时候只用了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;
        }
    }

转载于:https://www.cnblogs.com/yezekun/p/3925759.html