状压BFS

发表于 | 分类于 |

##hdu1429

第一次做状态压缩后的BFS，无非就是需要把某些状态压缩成二进制来储存以防爆内存

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#define LL long long
#define MOD 786433
#define PI acos(-1.0)
using namespace std;

int n,m,t,dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1},vis[22][22][1 << 10];
char mapp[22][22];

struct node
{
    int x,y,key,ti;
}st;

bool check(int x,int y)
{
    if(x && x <= n && y && y <= m)
        return true;
    return false;
}

int bfs()
{
    queue<node> q;
    st.key = 0,st.ti = 0;
    q.push(st);
    while(!q.empty())
    {
        node te = q.front();
        if(te.ti >= t )
            return -1;
        if(mapp[te.x][te.y] == '^')
            return te.ti;
        q.pop();
        for(int i = 0;i < 4;i++)
        {
            if(!check(te.x + dx[i],te.y + dy[i]))
                continue;
            char now = mapp[te.x + dx[i]][te.y + dy[i]];
            if(now == '^')
            {
                if(te.ti + 1 < t)
                    return te.ti + 1;
                else
                    return -1;
            }
            else if(now == '*')
            {
                continue;
            }
            else if(now >= 'A' && now <= 'J')
            {
                int move = now - 'A';
                node sv;
                if((te.key >> move) & 1)
                {
                    sv.x = te.x + dx[i],sv.y = te.y + dy[i];
                    sv.key = te.key,sv.ti = te.ti + 1;
                    if(!vis[sv.x][sv.y][sv.key])
                    {
                        vis[sv.x][sv.y][sv.key] = 1;
                        q.push(sv);
                    }

                }
            }
            else if(now >= 'a' && now <= 'j')
            {
                int move = now - 'a';
                node sv;
                if(te.key >> move & 1)
                {
                    sv.x = te.x + dx[i],sv.y = te.y + dy[i];
                    sv.key = te.key,sv.ti = te.ti + 1;
                    if(!vis[sv.x][sv.y][sv.key])
                    {
                        vis[sv.x][sv.y][sv.key] = 1;
                        q.push(sv);
                    }
                }
                else
                {
                    sv.x = te.x + dx[i],sv.y = te.y + dy[i];
                    sv.key = te.key | (1 << move),sv.ti = te.ti + 1;
                    if(!vis[sv.x][sv.y][sv.key])
                    {
                        vis[sv.x][sv.y][sv.key] = 1;
                        q.push(sv);
                    }
                }
            }
            else
            {
                node sv;
                sv.x = te.x + dx[i],sv.y = te.y + dy[i];
                sv.key = te.key,sv.ti = te.ti + 1;
                if(!vis[sv.x][sv.y][sv.key])
                {
                    vis[sv.x][sv.y][sv.key] = 1;
                    q.push(sv);
                }
            }
        }
    }
    return -1;
}

int main(){
    while(~scanf("%d%d%d",&n,&m,&t))
    {
        memset(vis,0,sizeof(vis));
        getchar();
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= m;j++)
            {
                scanf("%c",&mapp[i][j]);
                if(mapp[i][j] == '@')
                {
                    st.x = i,st.y = j;
                }   
            }
            getchar();
        }
        printf("%d\n",bfs());
    }
    return 0;
}

需要注意的地方就是vis标记的时候标记的值是x,y,key这样才是正确的标记方法。

另外还有一点就是以前我bfs的时候都是把四种情况分开来写，以后最好都把所有的情况都写在数组里面，然后一个for循环遍历就可以了。

##ZOJ2050
题意是给你一个4*4的棋盘，上面有黑白棋，每次你可以选择一个棋子，改变上下左右以及自己这个位置的颜色，要求最少几次之后可以使所有的棋子都为同色。同样也是状压bfs，把16颗棋子的颜色压缩到一个int值里面，巧用位运算即可，wa了几次……竟然是因为把大写的I写成了i，我也是醉了。不过自己对于位运算还是不够理解啊，还需努力。

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cstdio>
#define ll long long
using namespace std;

int st,vis[(1 << 17)];

int change(int x,int w)
{
    x ^= (1 << w);
    if(w > 3)
    {
        x ^= (1 << (w - 4));
    }
    if(w < 12)
    {
        x ^= (1 << (w + 4));
    }
    if(w % 4)
    {
        x ^= (1 << (w - 1));
    }
    if(w % 4 < 3)
    {
        x ^= (1 << (w + 1));
    }
    return x;
}

int bfs()
{
    queue<pair<int,int> >q;
    pair<int,int>stt;
    stt.first = st,stt.second = 0;
    //cout << st << endl;
    q.push(stt);
    vis[st] = 1;
    if(st == 0 || st == 65535)
        return 0;
    while(!q.empty())
    {
        pair<int,int> te = q.front();
        q.pop();
        for(int i = 0;i < 16;i++)
        {
            int now = change(te.first,i);
            if(now == 0 || now == 65535)
                return te.second + 1;
            if(vis[now])
                continue;
            vis[now] = 1;
            q.push(make_pair(now,te.second + 1));
        }
    }
    return -1;
}

int main(){
    int t,ok = 0;
    cin >> t;
    while(t--)
    {
        if(ok)
            cout << endl;
        else
            ok = 1;
        memset(vis,0,sizeof(vis));
        st = 0;
        for(int i = 0;i < 4;i++)
        {
            char s[11];
            scanf("%s",s);
            for(int j = 0;j < 4;j++)
            {
                if(s[j] == 'b')
                {
                    st |= (1 << (i * 4 + j));
                }
            }
        }
        //cout << st << endl;
        int ou = bfs();
        if(ou == -1)
            cout << "Impossible\n";
        else
            cout << ou << endl;
    }
    return 0;
}

热评文章