Newton – Épreuve régionale 2014

É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.