Algorithm (BFS with BitSet)
- We can construct a graph $G = (V, E)$ where $V$ represents board configuration and there exists an edge between any two node $v, u$ if and only if $v$ can be flipped to $u$ using the method described in the problem.
- Then the problem reduces to finding the shortest path from $v_0$ and $v_e$, both of which are deterministic.
- Since $G$ is unweighted, we can use the good old BFS to solve this issue.
- Note that we can use a BitSet to represent the board. This will speed things up by quite a bit.
- Time Complexity is $O(2^{18})$ since there are at most 9 cells and the graph could be complete.
Code
namespace utils::dynamic_bitset {
template <typename set_t = int, typename... Ts, typename std::enable_if_t<std::conjunction_v<std::is_same<int, Ts>...>>* = nullptr>
int flip(set_t mask, Ts... arg) { return ((mask ^= (1 << arg)), ...); }
template <typename set_t = int, typename... Ts, typename std::enable_if_t<std::conjunction_v<std::is_same<int, Ts>...>>* = nullptr>
bool test(set_t mask, Ts... arg) { return ((mask & (1 << arg)) && ...); }
template <typename set_t = int, typename T, typename std::enable_if_t<std::conjunction_v<std::is_same<int, T>>>* = nullptr>
int count_upto(set_t mask, T n) {
int acc = 0;
for (int i = 0; i < n; i++)
if ((mask & (1 << i)) > 0) acc++;
return acc;
};
template <typename set_t = int>
void assign_inplace(set_t* mask, int pos, int n) {
if ((test(*mask, pos) and n == 0)
or (not test(*mask, pos) and n == 1))
*mask = flip(*mask, pos);
}
}
class Solution {
public:
int minFlips(vector<vector<int>>& mat) {
using namespace utils::dynamic_bitset;
const int R = size(mat), C = size(mat[0]);
const array<int, 4> dr {1, -1, 0, 0};
const array<int, 4> dc {0 ,0, 1, -1};
auto id = [&](int r, int c) {
return r * C + c;
};
const auto initial_board = [&] {
int self = 0;
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c)
assign_inplace(&self, id(r, c), mat[r][c]);
return self;
}();
const int target_board = 0;
auto valid = [&](int r, int c) {
return r >= 0 and r < R and c >= 0 and c < C;
};
auto flip_board = [&](int board, int r, int c) {
auto old_board = board;
board = flip(board, id(r, c));
for (int i = 0; i < 4; ++i) {
const auto [nr, nc] = tuple(r + dr[i], c + dc[i]);
if (valid(nr, nc))
board = flip(board, id(nr, nc));
}
return board;
};
struct state_t {
mutable deque<int> Q;
mutable optional<int> D[1 << 10];
};
const auto solution = [&] {
const auto [Q, D] = state_t{{initial_board}, {}};
for (D[initial_board] = 0; not empty(Q);) {
const auto cur_board = Q.front();
Q.pop_front();
if (cur_board == target_board)
return *D[cur_board];
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c) {
if (const auto next_board = flip_board(cur_board, r, c); not D[next_board]) {
D[next_board] = *D[cur_board] + 1;
Q.emplace_back(next_board);
}
}
}
return -1;
}();
return solution;
}
};