Official Analysis (C++)

Explanation

We can use BFS to explore each blob, starting from an unvisited #. During BFS, we can calculate the blob’s area by counting the number of # visited and determine its perimeter by analyzing the surroundings of each #.

The perimeter is determined by summing the number of sides of all cells that are either adjacent to a # or are on the boundary.

As we traverse the grid, we can initiate a BFS for each unvisited # to compute the area and perimeter of all blobs. Within the BFS, for each #, we start by assuming that all four of its sides contribute to the perimeter. We then reduce this count by one for each neighboring #, since shared edges do not add to the perimeter.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
from collections import deque
from typing import List, Tuple

# Movement directions (up, down, left, right)
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(
	row: int, col: int, grid: List[str], visited: List[List[bool]]
) -> Tuple[int, int]: