leetcode

0 class Solution {

1 public:

2 int minFlips(const vector<vector<int>> &mat) const {

3 static const int offset[] = {-1, 0, 1, 0, -1};

4 const int n = size(mat), m = size(mat[0]);

5 unsigned res = -1;

6

7 const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };

8

9 for (unsigned mask = 0; mask < 1 << (n * m); mask++) {

10 auto grid = mat;

11

12 for (unsigned k = 0, crnt = mask; crnt; crnt >>= 1, k++) {

13 if (!(crnt & 1)) continue;

14

15 const int a = k / m, b = k % m;

16 for (int k = 0; k < 4; k++) {

17 const int x = a + offset[k + 1];

18 const int y = b + offset[k];

19

20 if (!valid(x, y)) continue;

21 grid[x][y] = !grid[x][y];

22 }

23 grid[a][b] = !grid[a][b];

24 }

25

26 for (int i = 0; i < n; i++) {

27 for (int j = 0; j < m; j++) {

28 if (grid[i][j]) goto next;

29 }

30 }

31

32 res = min(res, (unsigned)popcount(mask));

33 next:;

34 }

35

36 return res;

37 }

38 };