Bidirectional Search

On a $3\times 3$ board, eight pieces are placed, each marked with one of the numbers from $1$ to $8$. One empty space remains on the board, represented by $0$. A piece next to the empty space can be moved into it. The problem is: given an initial layout (initial state) and a target layout (for simplicity, let the target state be $123804765$), find a minimum-step sequence of moves that transforms the initial layout into the target layout.

It is easy to think of brute-force BFS. Brute-force BFS does not time out on this problem either. However, this is used as an example of bidirectional simultaneous search. We can use two BFSs: one searches forward from the initial state, and the other searches backward from the terminal state. Alternating between the two BFSs greatly reduces the size of the search trees. When one BFS finds a state already found by the other BFS, the answer is obtained.

#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;

struct State {
  int A[3][3];
  State() = default;

  State(string s) {
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        A[i][j] = s[i * 3 + j] - '0';
      }
    }
  }

  friend bool operator<(const State &a, const State &b) {
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        if (a.A[i][j] != b.A[i][j]) {
          return a.A[i][j] < b.A[i][j];
        }
      }
    }
    return false;
  }
};

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void bfs(queue<State> &q, map<State, int> &m1, map<State, int> &m2) {
  auto u = q.front();
  q.pop();
  int xx, yy;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (u.A[i][j] == 0) {
        xx = i;
        yy = j;
      }
    }
  }
  for (int i = 0; i < 4; i++) {
    int tx = dir[i][0] + xx, ty = dir[i][1] + yy;
    if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3) {
      auto v = u;
      swap(v.A[xx][yy], v.A[tx][ty]);
      if (m2.count(v)) {
        cout << m1[u] + m2[v] << endl;
        exit(0);
      }
      if (!m1.count(v)) {
        m1[v] = m1[u] + 1;
        q.push(v);
      }
    }
  }
}

int main() {
  string I, O;
  cin >> I;
  O = "123804765";
  State in = I, ou = O;
  queue<State> q1, q2;
  map<State, int> mp1, mp2;
  q1.push(in);
  mp1[in] = 0;
  q2.push(ou);
  mp2[ou] = 1;
  if (I == O) {
    cout << 0;
    return 0;
  }
  while (1) {
    bfs(q1, mp1, mp2);
    bfs(q2, mp2, mp1);
  }
  return 0;
}

There are $n$ lights, each connected to several lights, and each light has a switch. If the switch on a light is pressed, the switch states of that light and all lights connected to it change. Initially all lights are off. You need to turn on all the lights and find the minimum number of switch presses.

$1\le n\le 35$.

If brute-force DFS is used to search the states of turning lights on and off, the time complexity is $O(2^{n})$, which clearly times out. However, with Meet in the middle, the time complexity can be optimized to $O(n2^{n/2})$. Meet in the middle first finds half of the states: namely, the states reachable using only switches numbered $1$ through $\mathrm{mid}$; it then finds the states reachable using only the other half of the switches. If the lights turned on by the first and second halves are complementary, merging the two halves gives a way to turn on all the lights. In the implementation, store the states of the first half and the minimum number of presses needed to reach each state in a map. When searching the second half, each time a solution is found, merge it with the complementary solution from the first half to update the answer.

#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

int n, m, ans = 0x7fffffff;
map<long long, int> f;
long long a[40];

int main() {
  cin >> n >> m;
  a[0] = 1;
  for (int i = 1; i < n; ++i) a[i] = a[i - 1] * 2;  // preprocessing

  for (int i = 1; i <= m; ++i) {  // process the input edges
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    a[u] |= ((long long)1 << v);
    a[v] |= ((long long)1 << u);
  }

  for (int i = 0; i < (1 << (n / 2)); ++i) {  // search the first half
    long long t = 0;
    int cnt = 0;
    for (int j = 0; j < n / 2; ++j) {
      if ((i >> j) & 1) {
        t ^= a[j];
        ++cnt;
      }
    }
    if (!f.count(t))
      f[t] = cnt;
    else
      f[t] = min(f[t], cnt);
  }

  for (int i = 0; i < (1 << (n - n / 2)); ++i) {  // search the second half
    long long t = 0;
    int cnt = 0;
    for (int j = 0; j < (n - n / 2); ++j) {
      if ((i >> j) & 1) {
        t ^= a[n / 2 + j];
        ++cnt;
      }
    }
    if (f.count((((long long)1 << n) - 1) ^ t))
      ans = min(ans, cnt + f[(((long long)1 << n) - 1) ^ t]);
  }

  cout << ans;

  return 0;
}