All problems

Tidy Paddy Fields

Medium · graph traversal

A farm is drawn as a rectangular grid of characters. A cell holding "#" is flooded paddy and a cell holding "." is dry bank.

A field is a group of paddy cells joined through shared edges: you can walk from any cell of the field to any other moving up, down, left or right over paddy only. Cells that only touch at a corner belong to different fields.

A field is tidy if its cells exactly fill a rectangle: no gaps inside it and no bumps sticking out of it. A field of a single cell is a tidy 1 x 1 rectangle.

Return the number of tidy fields in grid.

Examples

Example 1

Input: grid = [["#", "#", "."], ["#", "#", "."], [".", ".", "#"]]

Output: 2

The 2 x 2 block and the lone cell in the corner are both rectangles.

Example 2

Input: grid = [["#", "#", "#"], ["#", ".", "#"], ["#", "#", "#"]]

Output: 0

The ring is one field, but the dry cell in the middle leaves a gap, so it is not a rectangle.

Example 3

Input: grid = [["#", "#", "."], ["#", ".", "."], [".", ".", "#"]]

Output: 1

The three connected cells in the corner form an L shape, so only the lone cell counts.

Constraints

• 1 <= rows, cols <= 25
• Every cell is either "#" (paddy) or "." (dry bank).
• All rows have the same length.