leetcode 岛屿系列
岛屿系列
网格DFS问题
DFS基本结构:
void dfs(int[][] grid, int r, int c) {
// 判断 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿,直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 将格子标记为「已遍历过」
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
695. 岛屿的最大面积[中等]
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)
class Solution {
public:
const vector<int> dx = {-1, 1, 0, 0};
const vector<int> dy = {0, 0, -1, 1};
void dfs (vector<vector<int>>& grid, int x, int y, int& area) {
if (grid[x][y] == 1) {
++area;
grid[x][y] = 2; // 遍历过
for (int i = 0; i < 4; ++i) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < grid.size() && my >= 0 && my < grid[0].size()) { // 边界值
dfs (grid, mx, my, area);
}
}
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int area = 0, tmp_area = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
dfs(grid, i, j, tmp_area);
area = max(area, tmp_area); // 自每个点出发的值的最大值
tmp_area = 0;
}
}
return area;
}
};
827. 最大人工岛[困难]
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后,grid 中最大的岛屿面积是多少?
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
...
将每个0变成1,重新采用695方式计算,但此性能很差;
本题不适合DFS算法。
463.岛屿周长[容易]
给定一个 row x col 的二维网格地图 grid ,其中:grid[i][j] = 1 表示陆地, grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。
岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。
class Solution {
constexpr static int dx[4] = {0, 1, 0, -1};
constexpr static int dy[4] = {1, 0, -1, 0};
public:
int dfs(int x, int y, vector<vector<int>> &grid, int n, int m) {
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
return 1;
}
if (grid[x][y] == 2) {
return 0;
}
grid[x][y] = 2;
int res = 0;
for (int i = 0; i < 4; ++i) {
int tx = x + dx[i];
int ty = y + dy[i];
res += dfs(tx, ty, grid, n, m);
}
return res;
}
int islandPerimeter(vector<vector<int>> &grid) {
int n = grid.size(), m = grid[0].size();
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1) {
ans += dfs(i, j, grid, n, m);
}
}
}
return ans;
}
};