M_sea

洛谷4289 [HAOI2008]移动玩具
LuoguBZOJ分析状压搜索。广告:hyj的题解代码//It is made by M_sea #include...
扫描右侧二维码阅读全文
22
2019/01

洛谷4289 [HAOI2008]移动玩具

Luogu

BZOJ

分析

状压搜索。

广告:hyj的题解

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

queue<int> Q;
int vis[1<<16],s[1<<16];

int main() {
    int S=0,T=0;
    for (re int i=0,j;i<16;++i) scanf("%1d",&j),S|=(j<<i);
    for (re int i=0,j;i<16;++i) scanf("%1d",&j),T|=(j<<i);
    Q.push(S); vis[S]=1,s[S]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=0;i<16;++i) {
            if (u&(1<<i)==0) continue;
            if (i>3&&(u&(1<<i-4))==0) {
                int v=u^(1<<i)^(1<<i-4);
                if (!vis[v]) s[v]=s[u]+1,vis[v]=1,Q.push(v);
            }
            if (i<12&&(u&(1<<i+4))==0) {
                int v=u^(1<<i)^(1<<i+4);
                if (!vis[v]) s[v]=s[u]+1,vis[v]=1,Q.push(v);
            }
            if (i%4&&(u&(1<<i-1))==0) {
                int v=u^(1<<i)^(1<<i-1);
                if (!vis[v]) s[v]=s[u]+1,vis[v]=1,Q.push(v);
            }
            if (i%4<3&&(u&(1<<i+1))==0) {
                int v=u^(1<<i)^(1<<i+1);
                if (!vis[v]) s[v]=s[u]+1,vis[v]=1,Q.push(v);
            }
            if (vis[T]) break;
        }
    }
    printf("%d\n",s[T]);
    return 0;
}
最后修改:2019 年 05 月 26 日 06 : 42 PM

发表评论