Find components


Submit solution

Points: 30 (partial)
Time limit: 3.0s
Python 3 5.0s
Memory limit: 256M

Author:
Problem type

You will be given an \(N \times M\) grid. Each cell can be either empty or occupied. Empty cells are denoted by '.' and occupied cells by '?'. Two cells are adjacent if they share a side.

In a move you can free any occupied cell (in other words, switch any '?' to '.'). We want to know, for each occupied cell, if we free this cell (and only this one) what would be the size of the connected identical component containing it.

A connected identical component is a maximum set of cells of the same nature (empty or occupied) where any two of them are connected by a path of adjacent cells. The size of a connected component is the number of cells it contains.

Input Specification

Input starts with a line containing two integers N and M (\(1 \leq N,M \leq 1000\)).

Then follows \(N\) lines containing a string of length \(M\) each, denoting the grid. The string contains either '.' or '?'.

Output Specification

Output \(x\) lines, Where \(x\) is the number of occupied cells of the grid. In line \(i\) you should output the size of the connected identical component containing the \(i^{th}\) occupied cell .

See notes for cells ordering.

Scoring

  • \( N \times M \leq 1000 \) (\(50\) Points).
  • \(1 \leq N,M \leq 1000\) (\(50\) Points).

Sample Input

4 3
??.
?..
..?
?.?

Sample Output

1
7
7
7
7
7

Notes

Cells are ordered this way :

1, 2, 3, 4,..., M M+1, M+2, ... , 2M . . (N-1)M + 1,.., NM


Comments


  • 0
    AkramElOmrani  commented on July 28, 2021, 2:51 p.m. edited

    I don't know where is the problem in my BFS please help