Libertés – Épreuve régionale 2015

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

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
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
Exemple de sortie
5
Commentaire

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

Exemple d'entrée
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
Exemple de sortie
4
Commentaire

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.

Exemple d'entrée
2 2
0 0
1 0
2 2
Exemple de sortie
1
Commentaire

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