Painting Board Piece Sizes
InterviewTime limit2sMemory limit128 MB
Given a grid with wall segments blocking movement between adjacent cells, find the largest and smallest connected region sizes using BFS or DFS.
Problem
A rectangular painting board has line segments drawn on boundaries between cells. Every segment is parallel to a side of the board, and you cannot move through a segment from one adjacent cell to the other.
These segments divide the board into one or more connected pieces. The size of a piece is the number of unit cells contained in that piece.
Given the board height, board width, and the drawn segments, find the size of the largest piece and the size of the smallest piece.
Input
The first line contains the board height N and width M, separated by a space. (1 <= N, M <= 500)
The second line contains the number of segments T. (1 <= T <= 1000)
Each of the next T lines contains four integers Sx Sy Ex Ey. This means there is a segment connecting the points (Sx, Sy) and (Ex, Ey). The top-left corner of the board is (0, 0), and the bottom-right corner is (N, M).
Output
Print the size of the largest piece on the first line.
Print the size of the smallest piece on the second line.
Hint
Treat each unit cell as a vertex. Block only the adjacencies crossed by the given segments, then search connected components to obtain their sizes.