代碼隨想錄圖論 第二天 | 695. 島嶼的最大面積 1020. 飛地的數(shù)量

一、695. 島嶼的最大面積

題目鏈接：https://leetcode.cn/problems/max-area-of-island/
思路：典型的遍歷模板題，我采用深度優(yōu)先，每塊島嶼遞歸遍歷的時候計數(shù)，遞歸完比較大小記錄最大值。

class Solution {int max = 0, k = 0;public int maxAreaOfIsland(int[][] grid) {for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1) {dfs(grid, i, j);max = Math.max(max, k);k = 0;}}}return max;}void dfs(int[][] grid, int x, int y) {if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) {return;}k++;grid[x][y] = 0;dfs(grid, x, y-1);dfs(grid, x, y+1);dfs(grid, x-1, y);dfs(grid, x+1, y);}
}

二、1020. 飛地的數(shù)量

題目鏈接：https://leetcode.cn/problems/number-of-enclaves/description/
思路：求飛地的數(shù)量其實就是求不與邊框相接的地塊數(shù)量，那么可以留一個標(biāo)識位flag，遞歸中發(fā)現(xiàn)不是飛地標(biāo)記一下，該次遞歸記得數(shù)就不累加了。

class Solution {// true表示沒有接觸邊界boolean flag = true;int num = 0;public int numEnclaves(int[][] grid) {int sum = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1) {dfs(grid, i, j);if (flag) {sum += num;}else {flag = true;}num = 0;}}}return sum;}void dfs(int[][] grid, int x, int y) {if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) {return;}if (x == 0 || y == 0 || x == grid.length-1 || y == grid[0].length-1) {flag = false;}num++;grid[x][y] = 0;dfs(grid, x, y-1);dfs(grid, x, y+1);dfs(grid, x-1, y);dfs(grid, x+1, y);}
}