Re: [閒聊] 每日LeetCode已回收
1254. Number of Closed Islands
給你一個只有0和1的二維陣列，0表示陸地1表示海，若一塊相連的陸地周圍都是海則他是
一個Closed Islands，求出共存在幾個Closed Islands。
Example :
https://assets.leetcode.com/uploads/2019/10/31/sample_3_1610.png
Input: grid =
[[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
只有從左邊數來的第一和第二個島嶼是Closed Islands，所以返回2。
https://assets.leetcode.com/uploads/2019/10/31/sample_4_1610.png
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1
思路：
1.如果一個島不是Closed Islands，那就表示這個島的邊界一定與陣列的邊界相鄰，
所以我們先掃描島嶼的最外圈把所有包含0的島嶼都去除。
2.去除最外圈的所有不同島嶼就是Closed Islands的數量了，若遇到某個點是0，可以用
dfs把所有相鄰的0都標記成非0並把res遞增，當每一格都走訪完就求得解了。
Java Code：
---------------------------------------
class Solution {
public int closedIsland(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; i++) {
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
for (int i = 0; i < n; i++) {
dfs(grid, 0, i);
dfs(grid, m - 1, i);
}
int res = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 0) {
dfs(grid, i, j);
res++;
}
}
}
return res;
}
private void dfs(int[][] grid, int y, int x) {
int m = grid.length;
int n = grid[0].length;
if (y < 0 || y == m || x < 0 || x == n || grid[y][x] != 0) {
return;
}
grid[y][x] = -1;
dfs(grid, y + 1, x);
dfs(grid, y - 1, x);
dfs(grid, y, x + 1);
dfs(grid, y, x - 1);
}
}
---------------------------------------
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680762516.A.8A9.html
※ 編輯: Rushia (122.100.75.86 臺灣), 04/06/2023 14:32:12
討論串 (同標題文章)
完整討論串 (本文為第 286 之 719 篇)：