Fuir la civilisation

Après trop d'années passées en tant que programmeur, vous décidez qu'il est temps de prendre votre retraite et de renouer avec la nature. Vous empaquetez toutes vos possessions non-technologiques (c'est à dire pas grand chose) et vous éloignez de la ville, d'Internet, de la civilisation et allez vers la campagne pour vivre une vie simple.

Malheureusement, avant de partir, vous devez écrire un dernier programme. Vous souhaitez aller aussi loin que possible de la civilisation --- dans l'une des zones les plus isolées qui soient connues de l'humanité. Vous possédez une carte de largeur W et de hauteur H. Cette carte vous indique où les zones de civilisation peuvent être trouvées.

Les zones les plus isolées sont les carrés qui sont à la distance Manhattan la plus éloignée de toute civilisation. La distance Manhattan entre deux carrés est la somme des distances haut/bas et gauche/droite, comme illustré ci-dessous.

Votre objectif est de déterminer à quelle distance se trouvent les zones les plus isolées de la civilisation.

Exemple

Considérez la carte ci-dessous, de largeur 10 et hauteur 11. Les zones de civilisation sont noircies. Les deux carrés marqués avec un X sont les carrés les plus isolés : aucun autre carré de la carte ne se situe plus loin de la civilisation que ceux-ci. Les carrés marqués ont chacun une distance manhattan de 3 par rapport à la civilisation la plus proche, donc la réponse au problème est 3.

Limites de temps et de mémoire (Python)

  • Temps : 3 s sur une machine à 1 GHz.
  • Mémoire : 30 000 ko.

Contraintes

  • 1 <= W, H <= 1 000, où W est la largeur de la carte, et H la hauteur;
  • on vous garantit qu'il y aura toujours au moins un carré de civilisation, et un carré sans civilisation.

De plus, 30% des points seront attribués à des tests dans lesquels les dimensions de la carte satisfont W, H <= 50.

Entrée

Votre programme doit lire sur l'entrée standard. La première ligne contiendra deux entiers positifs W et H, séparés par un espace. Les H lignes suivantes contiendront chacune W entiers. Chacun de ces entiers sera soit un 1, indiquant la présence de civilisation, soit un 0, indiquant l'absence de civilisation.

Sortie

Votre programme doit écrire une seule ligne sur la sortie standard. Cette ligne doit contenir un simple entier, donnant la distance Manhattan de la civilisation au carré le plus isolé de la carte.

Exemple

entrée : 

10 11
1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 1 0 0 1
1 0 0 0 0 0 0 1 1 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 0 0 0
1 1 0 0 0 1 1 1 0 0
1 1 0 0 1 1 1 0 0 1
1 0 1 1 1 1 0 0 0 1
1 0 0 1 1 0 0 0 0 1
0 0 1 1 0 0 0 0 0 1
0 0 1 1 1 1 1 1 1 1

sortie : 

3

Commentaires

Calcul du score

Le score pour chaque test d'entrée sera de 100% si la bonne réponse est affichée, ou 0% sinon.

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