#K1936. Find the Smallest Colored Rectangle

    ID: 24625 Type: Default 1000ms 256MiB

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.

## sample
6 8
........
..##....
..###...
...#....
...#....
........
1 2 4 4

</p>