Installation du camping

Rien de tel que de faire du camping pour profiter de la nature. Cependant sur Algoréa, les moustiques sont particulièrement pénibles et il faut faire attention à l'endroit où l'on s'installe, si l'on ne veut pas être sans cesse piqué.

Vous disposez d'une carte sur laquelle est indiquée, pour chaque parcelle de terrain, si le nombre de moustiques est supportable ou non. Votre objectif est de trouver le plus grand camping carré évitant les zones à moustiques qu'il est possible de construire.

TIME AND MEMORY LIMITS (Python)

  • Time: 2s on a 1GHz machine.
  • Memory: 64,000 KB.

CONSTRAINTS

1 <= nbLignes, nbColonnes <= 350

INPUT

  • Sur la première ligne : deux entiers nbLignes et nbColonnes
  • Les nbLignes lignes suivantes comportent chacun nbColonnes entiers compris entre 0 et 1 séparés par des espaces. 0 signifie qu'il n'y a pas de moustiques et 1 qu'il y a des moustiques

OUTPUT

Un unique entier : la taille maximale du côté d'un carré ne comportant que des 0 et dont les bords sont parallèles aux axes.

EXAMPLEs

EXAMPLE 1

input: 

6 7
1 0 0 1 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 1
1 0 0 0 1 0 1

output: 

4

EXAMPLE 2

input: 

5 7
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
1 1 1 1 1 0 0
1 1 1 1 1 0 0

output: 

3
Source: https://www.france-ioi.org.