[695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/)

--- tags: leetcode --- # [695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/) --- # My Solution ## Solution 1: DFS ### The Key Idea for Solving This Coding Question ### C++ Code 1 ```cpp= #define WHITE (0) #define GRAY (1) #define BLACK (2) #define LAND (1) #define WATER (0) class Solution { public: int maxAreaOfIsland(vector<vector<int>> &grid) { int rows = grid.size(), cols = grid[0].size(), maxArea = 0; vector<vector<int>> state(rows, vector<int>(cols, WHITE)); for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (state[r][c] == WHITE && grid[r][c] == LAND) { maxArea = max(maxArea, dfs(grid, state, r, c, rows, cols)); } } } return maxArea; } private: int dfs(vector<vector<int>> &grid, vector<vector<int>> &state, int r, int c, int rows, int cols) { if (r < 0 || rows <= r || c < 0 || cols <= c || state[r][c] != WHITE || grid[r][c] != LAND) { return 0; } state[r][c] = GRAY; int area = 1; area += dfs(grid, state, r - 1, c, rows, cols); area += dfs(grid, state, r + 1, c, rows, cols); area += dfs(grid, state, r, c - 1, rows, cols); area += dfs(grid, state, r, c + 1, rows, cols); state[r][c] = BLACK; return area; } }; ``` ### C++ Code 2 ```cpp= #define LAND (1) #define WATER (0) class Solution { public: int maxAreaOfIsland(vector<vector<int>> &grid) { rows = grid.size(); cols = grid[0].size(); vector<vector<bool>> visited(rows, vector<bool>(cols, false)); int maxArea = 0; for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (!visited[r][c] && grid[r][c] == LAND) { int area = dfs(grid, visited, r, c); if (maxArea < area) { maxArea = area; } } } } return maxArea; } private: int rows; int cols; int dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int r, int c) { vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int area = 1; visited[r][c] = true; for (auto &dir : dirs) { int nextR = r + dir[0], nextC = c + dir[1]; if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC || visited[nextR][nextC] || grid[nextR][nextC] != LAND) { continue; } area += dfs(grid, visited, nextR, nextC); } return area; } }; ``` ### Time Complexity $O(rows \cdot cols)$ ### Space Complexity $O(rows \cdot cols)$ ## Solution 2: BFS ### The Key Idea for Solving This Coding Question ### C++ Code 1 ```cpp= #define WHITE (0) #define GRAY (1) #define BLACK (2) #define LAND (1) #define WATER (0) struct cell { int r; int c; cell(int r, int c) : r(r), c(c) {} }; class Solution { public: int maxAreaOfIsland(vector<vector<int>> &grid) { int rows = grid.size(), cols = grid[0].size(), maxArea = 0; vector<vector<int>> state(rows, vector<int>(cols, WHITE)); for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (state[r][c] == WHITE && grid[r][c] == LAND) { maxArea = max(maxArea, bfs(grid, state, r, c, rows, cols)); } } } return maxArea; } private: int bfs(vector<vector<int>> &grid, vector<vector<int>> &state, int r, int c, int rows, int cols) { queue<cell> q; int area = 1; vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; q.push(cell(r, c)); state[r][c] = GRAY; while (!q.empty()) { int qLen = q.size(); for (int i = 0; i < qLen; ++i) { cell curr = q.front(); q.pop(); for (auto &dir : dirs) { int nextR = curr.r + dir[0], nextC = curr.c + dir[1]; if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC || state[nextR][nextC] != WHITE || grid[nextR][nextC] != LAND) { continue; } ++area; q.push(cell(nextR, nextC)); state[nextR][nextC] = GRAY; } state[curr.r][curr.c] = BLACK; } } return area; } }; ``` ### C++ Code 2 ```cpp= struct cell { int r; int c; cell(int r, int c) : r(r), c(c) {} }; #define LAND (1) #define WATER (0) class Solution { public: int maxAreaOfIsland(vector<vector<int>> &grid) { rows = grid.size(); cols = grid[0].size(); vector<vector<bool>> visited(rows, vector<bool>(cols, false)); int maxArea = 0; for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (!visited[r][c] && grid[r][c] == LAND) { int area = bfs(grid, visited, r, c); if (maxArea < area) { maxArea = area; } } } } return maxArea; } private: int rows; int cols; int bfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int r, int c) { vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; queue<cell> q; int area = 1; q.push(cell(r, c)); visited[r][c] = true; while (!q.empty()) { cell curr = q.front(); q.pop(); for (auto &dir : dirs) { int nextR = curr.r + dir[0], nextC = curr.c + dir[1]; if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC || visited[nextR][nextC] || grid[nextR][nextC] != LAND) { continue; } area += 1; q.push(cell(nextR, nextC)); visited[nextR][nextC] = true; } } return area; } }; ``` ### Time Complexity $O(rows \cdot cols)$ ### Space Complexity $O(rows \cdot cols)$ # Miscellane [2101. Detonate the Maximum Bombs](https://leetcode.com/problems/detonate-the-maximum-bombs/)