广搜题解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Grid = array< array<bool, 4>, 4 >;
ll dx[] = {0, 0, 1, -1};
ll dy[] = {1, -1, 0, 0};
Grid g;
queue< pair<Grid, ll> > qu;
set<Grid> vis;
bool check(const Grid& g) {//判断灯是否全点了
  for (ll i=1;i<=3;i++) {
    for (ll j=1;j<=3;j++) {
      if (g[i][j]==false) return false;
    }
  }
  return true;
}
Grid opt(Grid g, ll x, ll y) {
    // 翻转第 g[x][y]
  g[x][y]=!g[x][y];
  for (ll i=0;i<4;i++) {
    ll nx = x + dx[i];
    ll ny = y + dy[i];
    if (nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3) {
      g[nx][ny] = !g[nx][ny];
    }
  }
  return g;
}
int main() {
  for (ll i = 1; i <= 3; i ++) {
    for (ll j = 1; j <= 3; j ++) cin >> g[i][j];
  }
  qu.push({g, 0});
  vis.insert(g);
  while (qu.size()) {
    auto nd = qu.front(); qu.pop();
    auto g = nd.first;
    ll step = nd.second;
    if (check(g)) {
      cout << step;
      exit(0);
    }
    for (ll i = 1; i <= 3; i ++) {
      for (ll j = 1; j <= 3; j ++) {
          // 当前这个点是 i 和 j
        auto g_ = opt(g, i, j);
          //去重
        if (vis.count(g_)) continue;
        vis.insert(g_);
        qu.push({g_, step + 1});
      }
    }
  }
  return 0;
}