---
title: leetcode 1284
tags: leetcode, bruce force
---

// https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/
class Solution {
private:
  int n, m, cnt[3][3], ans, ans_min;

  vector<vector<int>> map;

  bool success;

  void dfs(int x, int y) {
    if (x == n && y == 0) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          if ((map[i][j] + cnt[i][j]) % 2) {
            return;
          }
        }
      }
      ans_min = min(ans, ans_min);
      success = true;
      return;
    }
    if (y == m) {
      dfs(x + 1, 0);
      return;
    }
    cnt[x][y]++;
    if (x - 1 >= 0)
      cnt[x - 1][y]++;
    if (x + 1 < n)
      cnt[x + 1][y]++;
    if (y - 1 >= 0)
      cnt[x][y - 1]++;
    if (y + 1 < m)
      cnt[x][y + 1]++;
    ans++;
    if (y == m - 1)
      dfs(x + 1, 0);
    else
      dfs(x, y + 1);

    cnt[x][y]--;
    if (x - 1 >= 0)
      cnt[x - 1][y]--;
    if (x + 1 < n)
      cnt[x + 1][y]--;
    if (y - 1 >= 0)
      cnt[x][y - 1]--;
    if (y + 1 < m)
      cnt[x][y + 1]--;
    ans--;
    if (y == m - 1)
      dfs(x + 1, 0);
    else
      dfs(x, y + 1);
  }

public:
  int minFlips(vector<vector<int>> &_map) {
    map = _map;
    n = map.size();
    m = map[0].size();
    success = false;
    ans = 0, ans_min = 9;
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        cnt[i][j] = 0;
      }
    }
    dfs(0, 0);
    if (success)
      return ans_min;
    return -1;
  }
};