Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「HAOI2008」移动玩具 - 状态压缩 + BFS

在一个 4×4 4 \times 4 的方框内摆放了若干个相同的玩具,要将这些玩具重新摆放成为理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动到的位置不能有玩具,求最小移动次数。

链接

BZOJ 1054

题解

将所有 16 16 个方框的状态存入一个整数的二进制位中,BFS 即可。

代码

#include <cstdio>
#include <climits>
#include <queue>

const int MAXN = 16;

inline unsigned int read() {
    unsigned int res = 0;
    for (int i = 0; i < 4; i++) {
        char s[4 + 1];
        scanf("%s", s);
        for (int j = 0; j < 4; j++) {
            if (s[j] == '1') res |= (1 << (4 * i + j));
        }
    }
    return res;
}

inline int bfs(unsigned int s, unsigned int t) {
    static int dist[1 << MAXN];
    for (int i = 0; i < (1 << MAXN); i++) dist[i] = INT_MAX;

    std::queue<unsigned int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        unsigned int v = q.front();
        q.pop();

        if (v == t) return dist[v];

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                int a = 4 * i + j;
                unsigned int va = !!(v & (1 << a));

                if (i != 3) {
                    int b = 4 * (i + 1) + j;
                    unsigned int vb = !!(v & (1 << b));
                    if (va != vb) {
                        unsigned int u = v;
                        if (vb) u |= (1 << a);
                        else u &= ~(1 << a);

                        if (va) u |= (1 << b);
                        else u &= ~(1 << b);

                        if (dist[u] > dist[v] + 1) {
                            dist[u] = dist[v] + 1;
                            q.push(u);
                        }
                    }
                }
                if (j != 3) {
                    int b = 4 * i + (j + 1);
                    unsigned int vb = !!(v & (1 << b));
                    if (va != vb) {
                        unsigned int u = v;
                        if (vb) u |= (1 << a);
                        else u &= ~(1 << a);

                        if (va) u |= (1 << b);
                        else u &= ~(1 << b);

                        if (dist[u] > dist[v] + 1) {
                            dist[u] = dist[v] + 1;
                            q.push(u);
                        }
                    }
                }
            }
        }
    }

    return -1;
}

int main() {
    unsigned int s = read(), t = read();
    printf("%d\n", bfs(s, t));
    return 0;
}
最近的文章

「HAOI2008」排名系统 - map + Splay

排名系统通常要应付三种请求:上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时,他原有的得分记录会被删除。为了减轻服务器负担,在返回某个区段内的排名记录时,最多返回 10 10 条记录。对于得分相同的,上传时间早的排名高。

于  BZOJ, HAOI, Splay, map, 数据结构 继续阅读
更早的文章

「HAOI2007」反素数 - 搜索

对于任何正整数 x x ,其约数的个数记作 g(x) g(x) ,例如 g(1)=1 g(1) = 1 g(6)=4 g(6) = 4 。如果某个正整数 x x 对于任何 i(0,x) i \in (0, x) 都满足 g(x)>g(i) g(x) > g(i) ,则称 x x 为反质数。

给定一个数 N N ,求最大的不超过 N N 的反质数。

于  BZOJ, HAOI, 搜索, 数学 继续阅读
comments powered by Disqus