#K1936. Find the Smallest Colored Rectangle
Find the Smallest Colored Rectangle
Find the Smallest Colored Rectangle
You are given a grid with h rows and w columns. Each cell in the grid is either .
representing an empty tile or #
representing a colored tile. Your task is to determine the smallest axis‐aligned rectangle that covers all the colored tiles.
If there is at least one colored tile, output the coordinates of the top-left and bottom-right corners of the rectangle. The grid rows and columns are 0-indexed. If no colored tile exists, output No colored tiles
.
Input Format
The first line contains two integers h and w (the number of rows and columns respectively). The next h lines each contain a string of length w, representing a row of the grid.
Output Format
If colored tiles exist, print four integers r1, c1, r2, c2 in one line, where (r1, c1) is the top-left and (r2, c2) is the bottom-right coordinate of the rectangle. Otherwise, output No colored tiles
.
Note: When representing formulas, use LaTeX format. For example, you can denote a cell's coordinate as \((r,c)\) and the grid size as \(h \times w\).
inputFormat
The first line contains two space-separated integers \(h\) and \(w\). The following \(h\) lines each contain a string of \(w\) characters (each character is either .
or #
).
outputFormat
If there is at least one colored tile, print four space-separated integers \(r_1\), \(c_1\), \(r_2\), \(c_2\) representing the coordinates of the top-left and bottom-right corners of the minimal rectangle covering all colored tiles (0-indexed). Otherwise, output No colored tiles
.
6 8
........
..##....
..###...
...#....
...#....
........
1 2 4 4
</p>