[LeetCode] Minimum Operations to Remove Adjacent Ones in Matrix

2123. Minimum Operations to Remove Adjacent Ones in Matrix

You are given a 0-indexed binary matrix grid. In one operation, you can flip any 1 in grid to be 0.

A binary matrix is well-isolated if there is no 1 in the matrix that is 4-directionally connected (i.e., horizontal and vertical) to another 1.

Return the minimum number of operations to make grid well-isolated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
int seen[301][301], match[301][301];
int dy[4]{-1,1,0,0}, dx[4]{0,0,-1,1};
int n, m;
int dfs(vector<vector<int>>& g, int y, int x, int& v) {
for(int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if(0 <= ny and ny < n and 0 <= nx and nx < m and g[ny][nx] and seen[ny][nx] != v) {
seen[ny][nx] = v;
if(match[ny][nx] == -1 or dfs(g, match[ny][nx] / m, match[ny][nx] % m, v)) {
match[ny][nx] = m * y + x;
match[y][x] = m * ny + nx;
return 1;
}
}
}
return 0;
}
public:
int minimumOperations(vector<vector<int>>& grid) {
memset(seen, -1, sizeof(seen));
memset(match, -1, sizeof(match));
n = grid.size(), m = grid[0].size();
int res = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(grid[i][j] and match[i][j] == -1)
res += dfs(grid,i,j,seen[i][j] = i * m + j);
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/04/21/PS/LeetCode/minimum-operations-to-remove-adjacent-ones-in-matrix/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.