LeetCode-695、Max Area of Islandhttps://leetcode.com/problems/max-area-of-island/
题目描述
You are given an m x n binary matrix grid、An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid、If there is no island, return 0.
Example 1:
Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]Output: 6Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]Output: 0
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j] is either 0 or 1.
解题思路 【C++】 1、stack循环
class Solution {public: int maxAreaOfIsland(vector>& grid) { int m = grid.size(), n = m ? grid[0].size() : 0, local_area, area = 0, x, y; vector direction{-1, 0, 1, 0, -1}; for (int i=0; i> island; island.push({i, j}); while (!island.empty()) { auto [r, c] = island.top(); island.pop(); for (int k=0; k<4; ++k) { x = r + direction[k], y = c + direction[k+1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) { grid[x][y] = 0; ++local_area; island.push({x, y}); } } } area = max(area, local_area); } } } return area; }};
2、class递归
class Solution {public: int maxAreaOfIsland(vector>& grid) { int result = 0, m = grid.size(), n = grid[0].size(); Utils utils; for(int i=0; i> &grid, int x, int y, int m, int n) { if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {return 0;} int count = 1; grid[x][y] = 0;//注意，在递归前需要先把当前格子更新为0 for (auto &step : steps) {count += dfs(grid, x+step[0], y+step[1], m, n);} return count; } };};
3、func递归
class Solution {public: int steps[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; inline bool IsInGrid(const vector> &grid, int i, int j) { return i >= 0 && j >= 0 && i < grid.size() && j < grid[i].size(); } void FindAreaOfIsland(vector> &grid, int i, int j, int &area) { if (!grid[i][j]) {return;} grid[i][j] = 0; area++; for (int k = 0; k < 4; ++k) { int new_i = i + steps[k][0]; int new_j = j + steps[k][1]; if (!IsInGrid(grid, new_i, new_j) || !grid[new_i][new_j]) {continue;} FindAreaOfIsland(grid, new_i, new_j, area); } return ; } int maxAreaOfIsland(vector>& grid) { int max_area = 0, area; for (int i = 0; i < grid.size(); ++i) { for (int j = 0; j < grid[i].size(); ++j) { if (!grid[i][j]) continue ; area = 0; FindAreaOfIsland(grid, i, j, area); if (area > max_area) max_area = area; } } return max_area; }};
整理一下
class Solution { vector direction{-1, 0, 1, 0, -1};public: int maxAreaOfIsland(vector>& grid) { if (grid.empty() || grid[0].empty()) {return 0;} int max_area = 0; for (int i=0; i>& grid, int r, int c) { if (grid[r][c] == 0) {return 0;} grid[r][c] = 0; int x, y, area = 1; for (int i=0; i<4; i++) { x = r + direction[i], y = c + direction[i+1]; if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) { area += dfs(grid, x, y); } } return area; }};
再换种思路
class Solution {public: int maxAreaOfIsland(vector>& grid) { if (grid.empty() || grid[0].empty()) {return 0;} int max_area = 0; for (int i=0; i>& grid, int r, int c) { if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0) {return 0;} grid[r][c] = 0; return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c) + dfs(grid, r, c + 1) + dfs(grid, r, c - 1); }};
【Java】
class Solution { public int maxAreaOfIsland(int[][] grid) { if (grid.length == 0 || grid[0].length == 0) {return 0;} int max_area = 0; for (int i=0; i= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {return 0;} grid[r][c] = 0; return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c) + dfs(grid, r, c + 1) + dfs(grid, r, c - 1); }}