Isaac – Regional event 2014

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

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

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.