Statement: no OJ can run. The code is only for reference. If you have any questions, please discuss with us

Title Source: Bailian 2019 postgraduate computer test

Title: A: Forest rangers build houses

Total time limit:
1000ms
Memory limit:
65536kB
describe
In a forest, the Ranger wants to build a house to live in, but he can't cut down any trees.
Now, please help him calculate the maximum area of the rectangular open space in the forest that can be used to build a house.
input
The protected forest is represented by a two-dimensional matrix, and its length and width are not more than 20 (i.e., < = 20).
The first row is two positive integers m,n, indicating that the matrix has m rows and n columns.
Then m lines, n integers in each line, 1 for trees and 0 for open spaces.
output
A positive integer indicating the largest rectangular open area in the forest that can be used to build a house.
sample input

4 5
0 1 0 1 1
0 1 0 0 1
0 0 0 0 0
0 1 1 0 1

sample output

5

Tips
The side length of submatrix can be 1, that is to say:
0 0 0 0 0
It's still a submatrix that can build a house.

Train of thought:
First, traverse to find the number of adjacent zeros on the left of the lattice of row i and column j.
Then traverse, set the length and width attributes for the grid in row i and column j, and compare them with the grid above to find the maximum area

Code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int map[21][21];

int main()
{
    memset(map,0,sizeof(map));//Initialize all to 0 
    int n , x , y , i , j , k , cur , _max , length , width;
    cin>>x>>y;
    for(i = 1 ; i <= x ; i++)
        for(j = 1 ; j <= y ; j++)
        {
            cin>>cur;
            if(cur == 0) map[i][j] = 1; //Enter 0 to assign 1 
        }
    for(i = 1 ; i <= x ; i++)
    {
        for(j = 1 ; j <=y ; j++)
        {
            if(map[i][j] == 1) map[i][j] = map[i][j-1] + 1;
        }
    }
/* Print test
    for(i = 1 ; i <= x ; i++)
    {
        for(j = 1 ; j <= y ; j++)
            cout<<map[i][j]<<" ";
        cout<<endl;
    }
*/
    _max = 0;

    for(i = 1 ; i <= x ; i++)
    {
        for(j = 1 ; j <= y ; j++)
        {
            if(map[i][j] != 0)
            {
                width = 1;
                length = map[i][j];
                _max = max(_max , width * map[i][j]);
                for(k = i - 1 ; k >= 1 ; k--)//Connect with the grid above to calculate the maximum area
                {
                    if(map[k][j] = 0) break;
                    width++;
                    length = min(length , map[k][j]);
                    _max = max(_max , length * width);
                }
            }
        }
    }
    cout<<_max<<endl;

}