Python BFS Algorithm for Maximum Area of Island

This code demonstrates a Python implementation of a Breadth-First Search (BFS) algorithm to determine the maximum area of an island within a grid composed of 0s and 1s. The algorithm efficiently explores connected land cells (1s) and calculates the area of each island.

class Solution:
    def __init__(self):
        self.dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]

    def bfs(self, grid, i, j):
        q = [(i, j)]
        area = 0
        visited = []
        while len(q)!=0:
            area += 1
            for i in range(len(q)):
                loc = q.pop(0)
                for dire in self.dirs:
                    next_x = dire[0] + loc[0]
                    next_y = dire[1] + loc[1]
                    if next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >= len(grid[0]):
                        continue
                    if grid[next_x][next_y]==1 and (next_x, next_y) not in visited:
                        visited.append((next_x, next_y))
                        q.append((next_x, next_y))
        return area

    def maxAreaOfIsland(self, grid) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    res = max(res, self.bfs(grid, i, j))
        return res

Algorithm Explanation:

1. Initialization:

   • dirs: A list of direction vectors representing up, down, left, and right. Used for exploring neighboring cells.

2. bfs(grid, i, j) Function:

   • This function performs BFS starting from a given cell (i, j) to calculate the area of the connected island.
   • q: A queue to store cells to be explored.
   • area: Stores the area of the island.
   • visited: A list to track visited cells.
   • Iteration:
     • The function iterates while the queue is not empty.
     • In each iteration, the first cell from the queue is popped and its unvisited neighbors are added to the queue.
     • The area is incremented for each visited cell.

3. maxAreaOfIsland(grid) Function:

   • This function iterates over all cells in the grid (m rows, n columns).
   • For each cell containing a 1, the bfs function is called to calculate the area of the corresponding island.
   • The maximum area encountered is stored in res.

Time Complexity: O(m * n) since each cell is visited at most once.

Example Usage:

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]]

solution = Solution()
max_area = solution.maxAreaOfIsland(grid)
print(f"Maximum Area of Island: {max_area}")  # Output: Maximum Area of Island: 6