Condition: On a square checkered paper of 8x8 cells, a part of cells is shaded (example in the figure). To determine the rectangle of maximum area inscribed into the lattice, not containing shaded cells. As a response, print the area of the rectangle and the coordinates of its two opposite vertices. (It is assumed that the rectangle with a maximum area of one.)
My solution: To begin with, I marked the shaded cells as ones, and the clean ones with zeros. The result is such a matrix:
The rectangle marked in red is the desired answer with the coordinates of the vertices (3,4) and (6,6) , the area of 15 cells.
Code: A function that determines whether shaded fields are in a given rectangle. If there is - returns false, if the rectangle is empty - true
bool is_hatch(int arr[m][n]) { bool res = true; for(int i=0; i<m; i++) { for(int j=0;j<n;j++) { if(arr[i][j] == 1) res = false; else res = true; } } return res; } Question: Tell me the algorithm for reducing the rectangle in case the function returns false, my guess is that the upper left corner is shifted to the right by 1 and down by 1. Similarly, the lower right corner is shifted to the left by 1 each time and up by 1 until There is a maximum area with a clean field. But I do not know how to implement this, heeelp
