Oil Skimming#3052
Thanks to a certain "green" resources company, a new profitable industry of oil skimming has emerged. There are large slicks of crude oil floating in the Gulf of Mexico, waiting to be collected by enterprising oil barons. One such oil baron has a special plane that can skim the surface of the water, collecting oil. However, each scoop covers a rectangle of m by m (either in the east/west or north/south direction). It is required that the rectangle is completely covered in oil; otherwise, the product is contaminated with pure ocean water and is thus unprofitable! Given a map of an oil slick, the oil baron wants you to compute the maximum number of scoops that may be extracted. The map is an N \times N grid where each cell represents a m square of water, and each cell is marked as either being covered in oil or as pure water.
The input begins with an integer (1 \le K \le 100) indicating the number of cases. Each case starts with an integer (1 \le N \le 600) indicating the size of the square grid. Each of the next lines contains characters, representing the cells of a row in the grid. A character '#' represents a cell with oil, and a character '.' represents a pure water cell.
For each case, output one line, formatted exactly as follows: "Case X: M" where is the case number (starting from ), and is the maximum number of scoops that may be extracted.
Esempio 1