Sponsored
Sponsored
In this approach, we will use Depth First Search (DFS) to explore the grid. The idea is to iterate over each cell in the grid and apply DFS when we encounter an unvisited cell that is a part of an island (i.e., grid value is 1). We will mark each visited cell to avoid revisiting. By keeping a count of the size of each island found, we can track the maximum size encountered.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.
Space Complexity: O(m * n), used for the visited matrix and recursion stack.
1#include <stdio.h>
2
3#define MAX 50
4
5int dfs(int grid[MAX][MAX], int visited[MAX][MAX], int m, int n, int i, int j) {
6 if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 || visited[i][j]) {
7 return 0;
8 }
9 visited[i][j] = 1;
10 return 1 + dfs(grid, visited, m, n, i + 1, j)
11 + dfs(grid, visited, m, n, i - 1, j)
12 + dfs(grid, visited, m, n, i, j + 1)
13 + dfs(grid, visited, m, n, i, j - 1);
14}
15
16int maxAreaOfIsland(int grid[MAX][MAX], int m, int n) {
17 int visited[MAX][MAX] = {0};
18 int max_area = 0;
19 for (int i = 0; i < m; i++) {
20 for (int j = 0; j < n; j++) {
21 if (grid[i][j] == 1 && !visited[i][j]) {
22 int area = dfs(grid, visited, m, n, i, j);
23 if (area > max_area) {
24 max_area = area;
25 }
26 }
27 }
28 }
29 return max_area;
30}
31
32int main() {
33 int grid[MAX][MAX] = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
34 {0,0,0,0,0,0,0,1,1,1,0,0,0},
35 {0,1,1,0,1,0,0,0,0,0,0,0,0},
36 {0,1,0,0,1,1,0,0,1,0,1,0,0},
37 {0,1,0,0,1,1,0,0,1,1,1,0,0},
38 {0,0,0,0,0,0,0,0,0,0,1,0,0},
39 {0,0,0,0,0,0,0,1,1,1,0,0,0},
40 {0,0,0,0,0,0,0,1,1,0,0,0,0}};
41 int m = 8, n = 13;
42 printf("Max area of island: %d", maxAreaOfIsland(grid, m, n));
43 return 0;
44}This C solution defines a DFS function that recursively counts connected land cells. A visited matrix is used to ensure cells are only counted once. The main function iterates over all cells in the grid and updates the maximum area found.
A Breadth First Search (BFS) approach can also be used to solve this problem by iteratively exploring each cell's neighbors using a queue and counting the size of islands found. By enqueueing all land cell neighbors for exploration and tracking maximum sizes found, we can also determine the maximum island area.
Time Complexity: O(m * n), since all cells are enqueued and dequeued once.
Space Complexity: O(m * n), required for the queue and the visited matrix.
1
This Python BFS solution uses a deque from the collections module to iteratively explore the grid in breadth-first manner, ensuring all discovered land is processed accurately.