Company: Amex
Difficulty: medium
Two Solar Power Plants We have a map of an area where two square solar power plants are planned to be built. The map is given as a rectangular matrix A of boolean values with N rows and M columns. A[R][C] is true if the place in the R-th row and C-th column can be covered by a solar power plant, and false if it is not possible. Each solar power plant must be built in a square shape, and every cell it covers must be a true cell. A single cell is already sufficient for a valid solar power plant. The two solar power plants cannot share any cell and must be of the same size . Given the map, report the area of each of the two biggest solar power plants that can be built. If two square solar power plants cannot be built at all, report 0 . Input Format The first line contains two space-separated integers N and M — the number of rows and the number of columns of the map. Each of the next N lines contains a string of exactly M characters describing one row of the map, from row 0 to row N - 1 .