TD 14 - Matrice et file

1 k-voisinage

1.1 Exercice 1 : Algorithme du \(k\)-voisinage dans une matrice

On considère une matrice \(M\) à \(n\) lignes et \(m\) colonnes, indexée de \(1\) à \(n\) pour les lignes et de \(1\) à \(m\) pour les colonnes.

  1. Donner le 3-voisinage de la case (4,2) dans cette matrice (les cases grises représentent des obstacles) :

    Grille 7×7 avec case rouge en (4,2)
Obstacles en : (2,3), (2,4), (2,5), (3,5), (4,1), (4,5), (5,2), (6,6), (7,3)

  2. Écrire un algorithme en pseudo-code qui reçoit en entrée :

    • La matrice \(M\) avec les dimensions \(n\) (nombre de lignes) et \(m\) (nombre de colonnes),
    • les coordonnées \((i,j)\) d’une case de la matrice,
    • un entier \(k\geq 1\),

    et qui affiche toutes les coordonnées des cases du \(k\)-voisinage de \((i,j)\) (c’est-à-dire toutes les cases \((x,y)\) atteignables à partir de \((i,j)\) en \(k\) déplacements).

NoteDéfinition : k-voisinage

Le k-voisinage d’une case \((i,j)\) est l’ensemble de toutes les cases atteignables en exactement \(k\) déplacements en utilisant les 4 directions (haut, bas, gauche, droite).

Distance de Manhattan : \(d((i,j), (x,y)) = |i-x| + |j-y|\)

Le k-voisinage contient toutes les cases à distance de Manhattan égale à \(k\).

Exemple pour k=1 : - Case \((3,3)\) : voisins = {(2,3), (4,3), (3,2), (3,4)}

Exemple pour k=2 : - Case \((3,3)\) : 8 voisins formant un losange

AstuceAlgorithme BFS pour k-voisinage

Utiliser une file pour un parcours en largeur (BFS) : 1. Enfiler la case de départ avec distance 0 2. Pour chaque case défilée : - Si distance = k : ajouter au résultat - Sinon : enfiler les voisins non visités avec distance+1 3. Continuer jusqu’à ce que toutes les cases de distance ≤ k soient visitées

2 En plus

2.1 Exercice 2 : Propagation sur une grille 2D 🏠

On considère une grille 2D composée de nombres entiers positifs.

L’origine, c’est-à-dire la case de coordonnées \((1,1)\), est située en haut à gauche.

Objectif : Écrire un algorithme Propagation(M, x, y) qui prend en paramètres la matrice M, et les coordonnées \((x, y)\) d’une case (lignes, colonnes) et effectue la propagation suivante :

  • On enfile les cases à une distance de 1 de la case \((x, y)\), puis de 2, de 3 jusqu’à rencontrer une case qui contient 0. (Attention : on enfile qu’une seule fois chaque case)
  • On soustrait \(1\) à tous ces k-voisins de la case \((x, y)\).

Exemple (Transformation de la grille avec Propagation(M, 1, 4)) :

Avant :                     Après :
|0 0 0 1 2 0 0|            |0 0 0 0 1 0 0|
|0 0 2 3 2 1 0|            |0 0 1 2 1 0 0|
|1 0 1 2 2 2 2|  -Prop->   |1 0 0 1 1 1 1|
|0 0 0 1 0 0 1|            |0 0 0 0 0 0 0|
|0 0 0 0 0 0 0|            |0 0 0 0 0 0 0|
|1 1 0 3 1 2 0|            |1 1 0 3 1 2 0|
  1. Proposez un algorithme Propagation(M, x, y) en pseudo-code
AstucePrincipe de propagation
  1. BFS depuis (x,y) : enfiler les voisins niveau par niveau
  2. Condition d’arrêt : s’arrêter quand on rencontre un 0
  3. Modification : décrémenter de 1 chaque case visitée
  4. Marquer les visités : utiliser une matrice booléenne pour éviter de revisiter

Complexité : \(O(n \times m)\) dans le pire cas (toute la grille)