À table ! – Regional event 2018

Level 3

Énoncé

La crêperie de Joseph Marchand est en désordre ! Il y a des tables partout, et il devient difficile de circuler pour servir les clients. En effet, il sera tout à fait malpoli qu'un serveur ait besoin de jouer à saute-mouton au-dessus des tables, risquant de mettre les pieds dans le plat ! Joseph n'est cependant pas sûr que cela se produise, il a placé les tables après un entraînement intensif à Tetris™ : il est devenu expert en agencement.

Joseph aimerait donc savoir combien d'emplacements libres dans son restaurant il lui est impossible d'accéder depuis ses cuisines. La crêperie sera représentée sous la forme d'une carte rectangulaire où '.' est un emplacement libre, et 'X' désigne une table qui bloque Joseph lors de son passage. Joseph a ses cuisines placées dans le coin haut à gauche de la grille correspondant à la case (0;0) où il est garanti qu'aucune table n'est jamais posée.

Entrée

Les dimensions du restaurant sont indiquées sur la première ligne : $N$ et $M$. Puis, sur les $N$ lignes qui suivent, il y a $M$ caractères : 'X' pour une table qui bloque le chemin de Joseph ou '.' pour une case libre.

Sortie

Un entier représentant le nombre d'emplacements libres inaccessibles pour Joseph depuis ses cuisines. À noter qu'une table n'est pas considérée comme un emplacement libre.

Contraintes

  • $1 \le N \le 100$
  • $1 \le M \le 100$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
6 5
.....
..XXX
.X...
.X.X.
.X...
.X...
Sample output
11
Note

Les tables bloquent l'accès à la partie inférieure droite du restaurant. Il y a donc 11 emplacements libres inaccessibles depuis les cuisines (les tables ne comptant pas).

Sample input
5 6
......
..X...
...X..
.X..X.
...X..
Sample output
0
Note

Aucune table ne bloque l'accès à un emplacement libre du restaurant.

Submit your solution

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