## Minimum Operations to Remove Adjacent Ones in Matrix

• Time:O(|V||E|) = O(m^2n^2)
• Space:O(mn)

## C++

``````class Solution {
public:
int minimumOperations(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
int ans = 0;
vector<vector<int>> seen(m, vector<int>(n));
vector<vector<int>> match(m, vector<int>(n, -1));

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1 && match[i][j] == -1) {
const int sessionId = i * n + j;
seen[i][j] = sessionId;
ans += dfs(grid, i, j, sessionId, seen, match);
}

return ans;
}

private:
const vector<int> dirs{0, 1, 0, -1, 0};

int dfs(const vector<vector<int>>& grid, int i, int j, int sessionId,
vector<vector<int>>& seen, vector<vector<int>>& match) {
const int m = grid.size();
const int n = grid[0].size();

for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] == 0 || seen[x][y] == sessionId)
continue;
seen[x][y] = sessionId;
if (match[x][y] == -1 ||
dfs(grid, match[x][y] / n, match[x][y] % n, sessionId, seen, match)) {
match[x][y] = i * n + j;
match[i][j] = x * n + y;
return 1;
}
}

return 0;
}
};
``````

## JAVA

``````class Solution {
public int minimumOperations(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
int ans = 0;
int[][] seen = new int[m][n];
int[][] match = new int[m][n];
Arrays.stream(match).forEach(A -> Arrays.fill(A, -1));

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1 && match[i][j] == -1) {
final int sessionId = i * n + j;
seen[i][j] = sessionId;
if (dfs(grid, i, j, sessionId, seen, match))
++ans;
}

return ans;
}

private static final int[] dirs = {0, 1, 0, -1, 0};

private boolean dfs(final int[][] grid, int i, int j, int sessionId, int[][] seen,
int[][] match) {
final int m = grid.length;
final int n = grid[0].length;

for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] == 0 || seen[x][y] == sessionId)
continue;
seen[x][y] = sessionId;
if (match[x][y] == -1 ||
dfs(grid, match[x][y] / n, match[x][y] % n, sessionId, seen, match)) {
match[x][y] = i * n + j;
match[i][j] = x * n + y;
return true;
}
}

return false;
}
}
``````

## Python

``````class Solution:
def minimumOperations(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dirs = [0, 1, 0, -1, 0]
seen = [[0] * n for _ in range(m)]
match = [[-1] * n for _ in range(m)]

def dfs(i: int, j: int, sessionId: int) -> int:
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if grid[x][y] == 0 or seen[x][y] == sessionId:
continue
seen[x][y] = sessionId
if match[x][y] == -1 or dfs(*divmod(match[x][y], n), sessionId):
match[x][y] = i * n + j
match[i][j] = x * n + y
return 1
return 0

ans = 0

for i in range(m):
for j in range(n):
if grid[i][j] == 1 and match[i][j] == -1:
sessionId = i * n + j
seen[i][j] = sessionId
ans += dfs(i, j, sessionId)

return ans
``````