POJ1753 位压缩 BFS

发表于 分类于

在很多情况下，我们可以用一个整数或者多个整数把多变的状态压缩，这样有利于空间上的优化，虽然在代码量上并不能得到多少的好处，但是遇到数据量大的时候还是可以有一定的效果的。

以 POJ1753 为例，这题是推荐题中的简单题了，一般的搜索完全可以过，甚至不用搜索。。。

我的方法是把 BFS 的状态压缩，由于每个牌面就 44 乘以 44，也就是 1616 个格子，每个格子只有黑白两种状态，用一个 int 型数就可以装下整个状态。

将牌面从上到下从左到右编号 00 到 1515，这样 int 型数从低位开始的第 i 位标记为 00 或者 11，分别表示白色和黑色，用位运算进行状态转移。

看下我的结构体：

1
2
3
4
5
6
struct Node {
  int code;
  int table;
  int depth;
  int last;
} start;
  • code 表示这个状态中各个格子是否被翻过，对应位如果为 11，则表示被按过，这种题目有一个显著的特点，那就是一个格子之多翻一次，否则和没翻是一个效果，这样我们记录了格子后就可以知道哪些格子被我们翻过，那些没有。
  • table 表示状态牌面的情况，第 i 位如果为 1 表示这位是黑色，否则为白色。
  • depth 表示从初状态到此状态的步数。
  • last 表示装移到这个状态翻转的格子编号，这样，我们每次都从最后一个翻转的格子之后的格子开始搜索，不会重复搜索。

另外，位压缩之后，写一个状态转移函数 hash()，用于转移状态。

1
2
3
4
5
6
7
8
9
int hash(int table, int op) {
  int st;
  st = (1 << op);
  if (op % 4 > 0) st |= (1 << (op - 1));
  if (op % 4 < 3) st |= (1 << (op + 1));
  if (op / 4 > 0) st |= (1 << (op - 4));
  if (op / 4 < 3) st |= (1 << (op + 4));
  return (table ^ st);
}

其中 tabletable 参数就是需要变换的牌面，opop 代表翻转的格子的编号，函数中的 st 变量表示需要翻转的位，如果第 i 位需要翻转，则这位就是 11，否则为 00，首先第 opop 位一定是需要翻转的，然后四个 if 判断格子的位置，当格子在最左边的时候，opmod  4op \mod 4 等于 00，最上边的时候，op4\frac{op}{4} 等于 00，以此类推，当格子不是最左边的时候，要对其左边 (op−1)(op-1) 位置的格子进行翻转，因此更新 stst 变量第 (op−1)(op-1) 位为 11，其他的类似。

在 BFS 函数中，末状态就是 1515 个 00 或者 1616 个 00 (216−12^{16}-1)，这样直接用判断整数是否相等就可以搞定。

主程序完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

struct Node {
  int code;
  int table;
  int depth;
  int last;
} start;

int hash(int table, int op) {
  int st;
  st = (1 << op);
  if (op % 4 > 0) st |= (1 << (op - 1));
  if (op % 4 < 3) st |= (1 << (op + 1));
  if (op / 4 > 0) st |= (1 << (op - 4));
  if (op / 4 < 3) st |= (1 << (op + 4));
  return (table ^ st);
}

int bfs() {
  Node node, next;
  queue<Node> q;
  node.code = 0;
  node.table = start.table;
  node.depth = 0;
  node.last = -1;
  if (node.table == 0 || node.table == ((1 << 16) - 1)) return 0;
  q.push(node);
  while (!q.empty()) {
    node = q.front();
    q.pop();
    for (int i = node.last + 1; i < 16; i++) {
      if ((node.code & (1 << i)) == 0) {
        next.code = (node.code | (1 << i));
        next.table = hash(node.table, i);
        next.depth = node.depth + 1;
        next.last = i;
        if (next.table == 0 || next.table == ((1 << 16) - 1)) return next.depth;
        q.push(next);
      }
    }
  }
  return -1;
}

int main() {
  char str[10];
  start.table = 0;
  for (int i = 0; i < 4; i++) {
    gets(str);
    for (int j = 0; j < 4; j++) {
      if (str[j] == 'b') {
        start.table |= (1 << (i * 4 + j));
      }
    }
  }
  int ret = bfs();
  if (ret == -1)
    printf("Impossible\n");
  else
    printf("%d\n", ret);
  return 0;
}

反思：这题 BFS 位压缩其实还可以优化，code 和 last 的作用是一样的，因为每次都从最后翻转的那位的后一位开始搜索，不用判断 code 变量，可以考虑将结构体变量再去掉一个。