Newton – Regional event 2014

Level 3

Énoncé

Isaac Newton aime les pommes. Ce n'est pas seulement leur forme magnifique, leur odeur alléchante ou leur goût délicieux, ou encore le fait qu'elles fondent délicatement dans la bouche de quiconque les croquent, mais également le fait qu'elles l'aient rendu célèbre en le faisant découvrir la gravité, par dessus le marché, qui les rend si fabuleuses.

Vous l'aurez compris, Isaac aime les pommes. Mais, Isaac est aussi un génie ! Voyant ainsi là une matière première de qualité pour ses recherches, Isaac décide d'inventer les automates cellulaires trois cents ans avant tout le monde, en agenceant des pommes dans son jardin.

Il a ainsi déterminé que pour que son automate soit stable, chaque génération devrait engendrer une pomme lorsqu'une case est entourée par trois pommes ou plus (on considère que chaque case est entourée par quatres autres).

Afin de savoir s'il aura assez de pommes, il cherche à déterminer combien de pommes seront créées à l'état suivant.

On vous donne donc le jardin de Newton en entrée (x pour une pomme, o sinon) et vous devez déterminer le nombre de pommes qui seront créées à la génération suivante (c'est à dire le nombre de cases vides entourées par 3 pommes ou plus).

Contraintes

  • 1 ≤ N ≤ 1 000 où N est la largeur et la longueur du jardin.

Entrée

  • Le nombre N, sur la première ligne,
  • Le jardin sur les N lignes suivantes (x pour une pomme, o sinon).

Sortie

Le nombre de pommes créées à la génération suivante.

Runtime constraints

Maximum memory usage
3000 kilobytes
Maximum execution time
3000 milliseconds

Input/output samples

Sample input
5
ooxoo
oxxxo
oxxxo
oxoxo
ooooo
Sample output
1
Note

Dans ce cas, le verger est de taille 25, dont 16 espaces à priori vides. Cependant, on remarque qu'un espace (avant-dernière ligne, colonne centrale) est adjacent à trois pommes. Une seule pomme créée à l'état suivant.

Sample input
5
ooxoo
oxxxo
oxxxo
oxoxo
oxxxo
Sample output
1

Submit your solution

You have to register or log in to be able to submit your solution.