Isaac – Épreuve régionale 2014

Niveau 3

Énoncé

Depuis de nombreuses générations, une légende se transmet de père en fils chez les Marchand.

Isaac est un ancêtre de Joseph. Il est dit que dès son plus jeune âge, Isaac adorait se cacher, alors sa mère le fouettait souvent (ou l'inverse, je ne sais plus).

Isaac était tellement chanceux que sa maison était l'endroit idéal pour s'adonner à ces joies. En effet, chez Isaac il y avait un immense grenier contenant de nombreuses salles (qu'on supposera carrées, chaque mur pouvant être commun à une ou deux salles) avec notamment des araignées, des malles, des machines à sous, des autels satanistes et autres objets de plaisir.

Heureusement pour lui, Isaac disposait d'une carte de son grenier (qu'on représentera sous forme de grille) pour s'y retrouver. Malheureusement pour lui, sa mère en disposait également. Mais par pure chance (oui, Isaac est un sacré veinard), il avait déjà creusé un mur pour ouvrir un passage vers une salle secrète (présente sur aucune carte). Mais par pure malchance, il en avait oublié la position. La seule chose dont il se souvient c'est que cette salle en touchait au moins 3 autres.

Afin de lui faire gagner du temps, indiquez à Isaac combien de positions sont candidates à la présence d'une salle secrète.

Contraintes

  • 1 <= N <= 1 000 où N est le nombre de salles possibles en largeur (et longueur) dans le grenier.

Entrée

  • Le nombre N, sur la première ligne,
  • La carte sur les N lignes suivantes (x pour une salle, o pour un espace a priori vide).

Sortie

Le nombre de salles secrètes envisageables.

Contraintes d'exécution

Utilisation mémoire maximum
3000 kilo-octets
Temps d'exécution maximum
3000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
ooxoo
oxxxo
oxxxo
oxoxo
ooooo
Exemple de sortie
1
Commentaire

Dans ce cas, le grenier est de taille 25, dont 16 espaces à priori vides. Cependant, on remarque qu'un espace (avant-dernière ligne, colonne centrale) est adjacent à trois salles. C'est le seul candidat pour une salle secrète.

Exemple d'entrée
5
ooxoo
oxxxo
oxxxo
oxoxo
oxxxo
Exemple de sortie
1