var closedIsland = function(grid) {
const n = grid.length, m = grid[0].length
let ans = 0
const dfs = (i, j) => {
if (i < 0 || i >= n || j < 0 || j >= m) return false
if (grid[i][j] === 1) return true
grid[i][j] = 1
const a = dfs(i + 1, j)
const b = dfs(i - 1, j)
const c = dfs(i, j + 1)
const d = dfs(i, j - 1)
return a && b && c && d
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] === 0 && dfs(i, j) === true) ans++
}
}
return ans
};
function closedIsland(grid: number[][]): number {
const n = grid.length, m = grid[0].length
let ans = 0
const dfs = (i, j) => {
if (i < 0 || i >= n || j < 0 || j >= m) return false
if (grid[i][j] === 1) return true
grid[i][j] = 1
const a = dfs(i + 1, j)
const b = dfs(i - 1, j)
const c = dfs(i, j + 1)
const d = dfs(i, j - 1)
return a && b && c && d
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] === 0 && dfs(i, j) === true) ans++
}
}
return ans
};
func closedIsland(grid [][]int) int {
n, m, ans := len(grid), len(grid[0]), 0
var dfs func(int, int) bool
dfs = func(i int, j int) bool {
if i < 0 || i >= n || j < 0 || j >= m {
return false
}
if grid[i][j] == 1 {
return true
}
grid[i][j] = 1
a, b, c, d := dfs(i + 1, j), dfs(i - 1, j), dfs(i, j + 1), dfs(i, j - 1)
return a && b && c && d
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 0 && dfs(i, j) == true {
ans++
}
}
}
return ans
}
class Solution {
public int closedIsland(int[][] grid) {
int n = grid.length, m = grid[0].length, ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) {
Queue<int[]> q = new ArrayDeque<int[]>();
q.offer(new int[]{i, j});
boolean closed = true;
while (q.isEmpty() == false) {
int[] node = q.poll();
int x = node[0], y = node[1];
if (x < 0 || y < 0 || x >= n || y >= m) {
closed = false;
continue;
}
if (grid[x][y] == 1) continue;
grid[x][y] = 1;
q.offer(new int[]{x + 1, y});
q.offer(new int[]{x - 1, y});
q.offer(new int[]{x, y + 1});
q.offer(new int[]{x, y - 1});
}
if (closed == true) ans++;
}
}
}
return ans;
}
}
const int dr[4][2] = ;
int closedIsland(int** grid, int gridSize, int* gridColSize){
int ans = 0;
int q[gridSize * gridColSize[0] * 5][2];
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < *gridColSize; j++) {
if (grid[i][j] == 0) {
int head = 0, tail = 1;
q[head][0] = i;
q[head][1] = j;
bool closed = true;
while (head < tail) {
int* node = q[head++];
int x = node[0], y = node[1];
if (x < 0 || x >= gridSize || y < 0 || y >= *gridColSize) {
closed = false;
continue;
}
if (grid[x][y] == 1) continue;
grid[x][y] = 1;
for (int k = 0; k < 4; k++) {
q[tail][0] = x + dr[k][0];
q[tail][1] = y + dr[k][1];
tail++;
}
}
if (closed == true) ans++;
}
}
}
return ans;
}
并查集
class UnionFind {
private:
vector<int> parent;
vector<int> sizes;
int cnt;
public:
UnionFind(int n) {
cnt = n;
parent = vector<int>(n, 0);
sizes = vector<int>(n, 1);
while (n--) parent[n] = n;
}
int find(int x) {
while (x != parent[x]) x = parent[parent[x]];
return x;
}
void connect(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX == rootY) return;
if (sizes[rootX] >= sizes[rootY]) {
parent[rootY] = rootX;
sizes[rootX]++;
} else {
parent[rootX] = rootY;
sizes[rootY]++;
}
cnt--;
}
int size() {
return cnt;
}
void minusCnt() {
cnt--;
}
};
class Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
UnionFind u(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) {
if (i + 1 < n && grid[i + 1][j] == 0) u.connect(i * m + j, (i + 1) * m + j);
if (j + 1 < m && grid[i][j + 1] == 0) u.connect(i * m + j, i * m + j + 1);
} else {
u.minusCnt();
}
}
}
unordered_set<int> rootSet;
for (int i = 0; i < n; i++) {
if (grid[i][0] == 0) rootSet.emplace(u.find(i * m));
if (grid[i][m - 1] == 0) rootSet.emplace(u.find(i * m + m - 1));
}
for (int j = 0; j < m; j++) {
if (grid[0][j] == 0) rootSet.emplace(u.find(j));
if (grid[n - 1][j] == 0) rootSet.emplace(u.find((n - 1) * m + j));
}
return u.size() - rootSet.size();
}
};
class UnionFind:
def __init__(self, n: int):
self.cnt = n
self.parents = [0] * n
self.sizes = [1] * n
while n > 0:
self.parents[n - 1] = n - 1
n -= 1
def size(self) -> int:
return self.cnt
def find(self, x: int) -> int:
while x != self.parents[x]: x = self.parents[self.parents[x]]
return x
def union(self, x: int, y: int):
rootX, rootY = self.find(x), self.find(y)
if rootX == rootY: return
if self.sizes[rootX] >= self.sizes[rootY]:
self.parents[rootY] = rootX
self.sizes[rootX] += 1
else:
self.parents[rootX] = rootY
self.sizes[rootY] += 1
self.cnt -= 1
def minusCnt(self):
self.cnt -= 1
class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
u = UnionFind(n * m)
for i in range(0, n):
for j in range(0, m):
if grid[i][j] == 0:
if i + 1 < n and grid[i + 1][j] == 0: u.union(i * m + j, (i + 1) * m + j)
if j + 1 < m and grid[i][j + 1] == 0: u.union(i * m + j, i * m + j + 1)
else: u.minusCnt()
rootSet = set()
for i in range(0, n):
if grid[i][0] == 0: rootSet.add(u.find(i * m))
if grid[i][m - 1] == 0: rootSet.add(u.find(i * m + m - 1))
for j in range(0, m):
if grid[0][j] == 0: rootSet.add(u.find(j))
if grid[n - 1][j] == 0: rootSet.add(u.find((n - 1) * m + j))
return u.size() - len(rootSet)
