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.
1using System.Collections.Generic;
public class Solution {
private int Bfs(int[][] grid, int i, int j) {
int[][] directions = new int[][] {
new int[] {1, 0},
new int[] {-1, 0},
new int[] {0, 1},
new int[] {0, -1}
};
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((i, j));
grid[i][j] = 0;
int area = 0;
while (queue.Count > 0) {
var (x, y) = queue.Dequeue();
area++;
foreach (var dir in directions) {
int newX = x + dir[0], newY = y + dir[1];
if (newX >= 0 && newX < grid.Length && newY >= 0 && newY < grid[0].Length && grid[newX][newY] == 1) {
queue.Enqueue((newX, newY));
grid[newX][newY] = 0;
}
}
}
return area;
}
public int MaxAreaOfIsland(int[][] grid) {
int maxArea = 0;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[0].Length; j++) {
if (grid[i][j] == 1) {
maxArea = Math.Max(maxArea, Bfs(grid, i, j));
}
}
}
return maxArea;
}
}The BFS approach in C# uses a queue to iteratively process land cells and calculate island areas. This approach ensures each cell is processed only after all its prior nodes are handled.