HDU3220 逆向思维的 BFS

这道题有两个重要的地方，一个是对题目的理解，合法的操作只有一种，那就是对相邻的两个状态不同的灯泡进行交换状态的操作，也就是说，相邻的灯泡如果都是亮着的或者暗着的，那么不能对这条边进行操作。

第二点，那就是由于所有的状态的目标状态都是一样的，那么我们就可以从目标状态进行 BFS，计算出其他状态到目标状态要多少步，注意当 BFS 的步数大于 $3$ 的时候，就不要将其子状态放入队列中，为了方便，之前将全部的状态的需要步数设置为 5，这样即使没有访问的状态，步数也是大于 $3$ 的，这个算法的时间复杂度是 $O(32^3)$，完全可以接受，之后就是 $O(1)$ 的查询。

为了方便 BFS，优化空间，运用位压缩，将 $16$ 个灯泡的状态用一个 int 来存放，高位存放低编号的灯泡，装换的时候就用异或运算即可。

数组 $x$ 和 $y$ 用来对应 $32$ 对相邻的灯泡

我的代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int MAX = 1 << 17;
const int x[32] = {0,  1, 3, 11, 10, 8,  10, 2, 8,  9, 9,  0, 0, 1, 3,  11,
                   10, 8, 9, 2,  12, 13, 13, 4, 14, 6, 12, 4, 5, 7, 15, 14};
const int y[32] = {1,  3,  11, 10, 8,  0, 2,  3, 9, 1, 11, 2, 4, 5,  7,  15,
                   14, 12, 13, 6,  13, 5, 15, 6, 6, 7, 4,  5, 7, 15, 14, 12};
const int aim = ((1 << 8) - 1);
int dist[MAX];

struct Node {
  int st;
  int depth;
};

int hash(const int& st, const int& op) {
  return st ^ ((1 << (15 - x[op])) | (1 << (15 - y[op])));
}

void bfs() {
  Node node, next;
  queue<Node> q;
  node.st = aim;
  node.depth = 0;
  dist[aim] = 0;
  q.push(node);
  while (!q.empty()) {
    node = q.front();
    q.pop();
    if (node.depth > 3) break;
    next.depth = node.depth + 1;
    for (int i = 0; i < 32; i++) {
      if ((node.st & (1 << (15 - x[i]))) != (node.st & (1 << (15 - y[i])))) {
        next.st = hash(node.st, i);
        if (dist[next.st] == 1000) {
          dist[next.st] = next.depth;
          q.push(next);
        }
      }
    }
  }
}

int main() {
  int t, cnt = 0;
  int a;
  int st;
  for (int i = 0; i < MAX; i++) {
    dist[i] = 1000;
  }
  bfs();
  scanf("%d", &t);
  while (t--) {
    cnt++;
    st = 0;
    for (int i = 0; i < 16; i++) {
      scanf("%d", &a);
      if (a == 1) st |= (1 << (15 - i));
    }
    a = dist[st];
    if (a > 3) {
      printf("Case #%d: more\n", cnt);
    } else {
      printf("Case #%d: %d\n", cnt, a);
    }
  }
  return 0;
}

总结：在搜索的时候，我们经常要想到是否有可以优化的方法，位压缩是一个很好的节约空间的方式，另外，这题不可能对每个状态正向 BFS，那样在多 case 的情况下肯定是 TLE 的，另外就是要仔细看题，理解题目的意思，对题目的理解如果错误，将会导致思路的定式，觉得自己肯定是对的，这样，在比赛的时候就会心慌，严重影响比赛的状态。