Find connected region sizes in matrix

Given an m x n grid of characters grid and a target character ch, implement: (1) sizeOfRegion(grid, r0, c0, ch) -> int that returns the size of the 4-directionally connected region containing (r0, c 0) if grid[r0][c0] == ch, otherwise 0. (2) countRegions(grid, ch) -> int that returns the number of distinct 4-directionally connected regions composed of ch in the entire grid. Constraints: 1 <= m, n <= 2000. Use DFS (recursive or iterative). Analyze time and space complexity, and discuss how to avoid recursion depth limits for worst-case inputs.

Size of Connected Region in Matrix

Given an m x n grid of characters grid, a starting cell (r0, c0), and a target character ch, return the size of the 4-directionally connected region of ch that contains (r0, c0).

A region is a maximal set of cells all equal to ch that are connected horizontally or vertically (not diagonally). If grid[r0][c0] != ch, return 0.

Use DFS (an explicit stack is preferred over recursion to avoid hitting recursion-depth limits — with m, n up to 2000 a worst-case fully-connected region can contain 4,000,000 cells, far exceeding the default recursion limit).

Constraints:

• 1 <= m, n <= 2000
• grid[i][j] is a single character
• 0 <= r0 < m, 0 <= c0 < n

Examples

Example 1

Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 0, 0, 'a')
Output: 3

Explanation: The 'a' region containing (0,0) covers (0,0),(0,1),(1,0). The lone 'a' at (2,2) is disconnected, so size is 3.

Example 2

Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 0, 2, 'b')
Output: 3

Explanation: The 'b' region containing (0,2) covers (0,2),(1,1),(1,2), size 3.

Hints

1. Connectivity is 4-directional (up/down/left/right), never diagonal.
2. If the starting cell does not equal ch, the region is empty — return 0 immediately.
3. Use an explicit stack instead of recursion: with m, n up to 2000 a region can hold 4,000,000 cells, blowing past Python's default recursion limit and any practical call-stack depth.
4. Mark a cell visited when you push it (not when you pop it) to avoid pushing the same cell multiple times.

Count Connected Regions of a Character

Given an m x n grid of characters grid and a target character ch, return the number of distinct 4-directionally connected regions composed entirely of ch in the whole grid.

Two ch cells belong to the same region if they are connected horizontally or vertically (not diagonally). Scan every cell once; whenever you encounter an unvisited ch cell, increment the count and flood-fill its entire region so it is not counted again.

Use DFS with an explicit stack to stay safe against recursion-depth limits at the maximum grid size.

Constraints:

• 1 <= m, n <= 2000
• grid[i][j] is a single character

Examples

Example 1

Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 'a')
Output: 2

Explanation: Two 'a' regions: the top-left cluster {(0,0),(0,1),(1,0)} and the isolated (2,2).

Example 2

Input: ([['a','a','b'],['a','b','b'],['c','c','a']], 'b')
Output: 1

Explanation: All 'b' cells {(0,2),(1,1),(1,2)} are connected, so 1 region.

Hints

1. Iterate over every cell; start a new region only at an unvisited cell equal to ch.
2. When you start a region, flood-fill it completely (DFS/BFS) so its other cells are not counted as new regions.
3. A shared visited matrix across the whole scan guarantees each region is counted exactly once.
4. Prefer an iterative stack over recursion: at m, n = 2000 a single region can span millions of cells.