Re: [閒聊] 每日LeetCode已回收
1020. Number of Enclaves
給你一個二維陣列裡面只有0和1，0表示海洋，1表示陸地。
每次可以從單元格的上下左右移動，或走出邊界。
求出不論走幾步都無法走出邊界的陸地面積。
思路：
1.跟昨天這題90%像 #1aBcQKYf (Marginalman) ，一樣是對邊緣做DFS把所有靠邊邊的
陸地都標記為非1。
2.再來遍歷原陣列並檢查有幾個1就好。
Java Code：
----------------------------------------
class Solution {
public int numEnclaves(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; i++) {
for (int j = 1; j < n; j++) {
if (grid[i][j] == 1) {
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] != 1) {
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/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680843787.A.AD8.html
推
04/07 13:12,
2年前
, 1F
04/07 13:12, 1F
討論串 (同標題文章)
完整討論串 (本文為第 287 之 719 篇)：