Libertés – Regional event 2015

Level 4

Énoncé

Le jeu de Go est un jeu de stratégie similaire aux échecs, durant lequel deux joueurs posent des pierres noires et blanches sur les intersections d'une grille. Pour gagner, il faut principalement encercler les pierres de l'adversaire pour créer des « territoires ».

Lorsque des pierres d'une même couleur sont adjacentes selon les lignes de la grille (une pierre a donc 4 voisins, sauf quand elle se trouve au bord du plateau, dans ce cas elle en a moins), elles forment une chaîne. On définit le nombre de libertés d'une chaîne par le nombre d'intersections vides immédiatement adjacentes à une chaîne.

Sur l'exemple suivant, la chaîne noire a 5 libertés, représentés par des points noirs :

On a aussi 2 chaînes blanches distinctes qui ont toutes les deux 4 libertés (avec une liberté en commun).

On vous donne un plateau sur lequel une partie est en cours, la position d'une pierre, vous devez afficher le nombre de libertés de la chaîne contenant la pierre en question.

Entrée

L'entrée contient plusieurs lignes :

  • Sur la première, la hauteur H et la largeur L du plateau
  • Sur la deuxième, les coordonnées l et c de la pierre (le coin en haut à gauche a pour coordonnées (0,0))
  • Sur les H lignes suivantes, L entiers (un pour chaque intersection de la ligne)

La convention pour les entiers représentant la grille est la suivante :

  • 0 : Pierre noire
  • 1 : Pierre blanche
  • 2 : Intersection vide

Sortie

Le nombre de libertés de la chaîne contenant la pierre donnée en entrée.

Contraintes

  • 2 ≤ H, L ≤ 1000
  • 0 ≤ l < H
  • 0 ≤ c < L
  • Les plateaux donnés en entrée ne sont pas nécessairement valides, ni atteignables selon les règles du jeu de Go, mais on va faire semblant.

Runtime constraints

Maximum memory usage
50000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
5 6
1 2
2 2 2 2 2 2
2 2 0 0 2 2
2 0 0 1 1 2
2 1 1 2 2 2
2 2 2 2 2 2
Sample output
5
Note

Il s'agit de l'exemple donné dans l'énoncé. La pierre (1, 2) est dans la chaîne noire.

Sample input
5 6
3 1
2 2 2 2 2 2
2 2 0 0 2 2
2 0 0 1 1 2
2 1 1 2 2 2
2 2 2 2 2 2
Sample output
4
Note

Encore l'exemple de l'énoncé. Ici, la pierre (3,1) se trouve dans la chaîne en bas à gauche, qui a 4 libertés.

Sample input
2 2
0 0
1 0
2 2
Sample output
1
Note

Attention aux bords ! Il n'y a qu'une seule intersection libre à côté de la pierre noire en (0, 0).

Submit your solution

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