chal_200.py

from collections import deque


class Solution(object):
    offsets = {"right": (0, 1), "left": (0, -1), "up": (-1, 0), "down": (1, 0)}
    directions = ["right", "left", "up", "down"]

    def is_neighbor_in_grid(self, neighbor, grid):
        return (
            neighbor[0] < len(grid)
            and neighbor[0] >= 0
            and neighbor[1] < len(grid[0])
            and neighbor[1] >= 0
        )

    def is_neighbor_land(self, neighbor, grid):
        return grid[neighbor[0]][neighbor[1]] == "1"

    def bfs(self, row, col, grid, visited):
        queue = deque()
        queue.append((row, col))
        visited.add((row, col))

        while queue:
            current_cell = queue.popleft()
            for direction in self.directions:
                row_offset, col_offset = self.offsets[direction]
                neighbor = (
                    current_cell[0] + row_offset,
                    current_cell[1] + col_offset,
                )
                if (
                    self.is_neighbor_in_grid(neighbor, grid)
                    and self.is_neighbor_land(neighbor, grid)
                    and neighbor not in visited
                ):
                    queue.append(neighbor)
                    visited.add(neighbor)

    def num_of_islands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        island_count = 0
        visited = set()

        if not grid:
            return 0

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == "1" and (row, col) not in visited:
                    self.bfs(row, col, grid, visited)
                    island_count += 1
        return island_count


# Test cases
sol = Solution()

grid_1 = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"],
]
assert sol.num_of_islands(grid_1) == 1

grid_2 = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "1", "1"],
]
assert sol.num_of_islands(grid_2) == 2

grid_3 = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]
assert sol.num_of_islands(grid_3) == 3

grid_4 = [
    ["1"],
]
assert sol.num_of_islands(grid_4) == 1


grid_5 = [
    ["1", "0"],
]
assert sol.num_of_islands(grid_5) == 1