On définit des matrices de la façon suivante :
from random import randint
def cree_matrice(n) :
""" retourne A matrice n sur n,
chaque coefficient de A est 0, 1 ou 2 (tirage au hasard).
"""
A = [ [ 0 for i in range(n)] for j in range(n) ]
for i in range(n) :
for j in range(n) :
A[i][j] = randint(0,2)
return A
def affiche_matrice(A) :
n = len(A)
for i in range(n) :
for j in range(n) :
print(A[i][j], end=' ')
print()
n = 7
A = cree_matrice(n)
affiche_matrice(A)
On obtient par exemple :
0 1 2 0 2 1 1 1 2 2 2 0 0 0 1 0 2 2 1 2 0 0 2 0 0 1 2 1 0 0 0 2 2 1 0 1 1 1 1 2 0 2 1 0 1 1 0 1 0
Deux coefficients x et y de même valeur a seront dits connexes :
- Si x et y ont même coordonnées,
- ou si on peut trouver une chaîne
de coefficients, tous de valeur a :
x = x0, x1, x2, ..., xp-1, y=xp
dans laquelle chaque xi est voisin de xi+1.
La notion de voisin est ici définie ainsi :
def voisins(n, i,j) :
"""
retourne les couples de coordonnées des voisins de la cellule (i,j)
dans une matrice n sur n.
i est le numéro de ligne (entre 0 et n-1).
j est le numéro de colonne (entre 0 et n-1).
"""
voisinage = []
decale = (-1, 0, 1)
for l in decale :
for c in decale :
if (l, c) != (0, 0) :
v = (i+l, j+c)
if -1 < v[0] < n and -1 < v[1] < n : voisinage.append(v)
return voisinage
print(voisins(5, 0, 1))
print(voisins(5, 1, 1))
On obtient :
[(0, 0), (0, 2), (1, 0), (1, 1), (1, 2)] [(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)]
Ce qui signifie que dans une matrice 5 sur 5, le coefficient (ligne 0, colonne 1) a 5 voisins de coordonnées (0, 0), (0, 2), (1, 0), (1, 1), (1, 2). Tandis que le coefficient (ligne 1, colonne 1) a 8 voisins.
Définir une procédure récursive prenant en argument une matrice A et le couple (ligne, colonne) d'un coefficient de la matrice.
- Si le coefficient ne vaut pas 0, la procédure ne fait rien.
- Si le coefficient vaut 0, la procédure retourne la matrice A dans laquelle tous les coefficients nuls connexes au coefficient choisi ont été remplacés par des 9.
- principe
- un code
- une application
On peut redéfinir la connexité de façon plus explicitement récursive :
x est connexe à y (≠ x) si x est voisin de y, ou si x est voisin d'un z lui-même connexe à y.
from random import randint
def cree_matrice(n) :
""" retourne A matrice carrée n sur n,
chaque coefficient de A est 0, 1 (tirage au hasard).
"""
A = [ [ 0 for i in range(n)] for j in range(n) ]
for i in range(n) :
for j in range(n) :
A[i][j] = randint(0,1)
return A
def affiche_matrice(A) :
n = len(A)
for i in range(n) :
for j in range(n) :
print(A[i][j], end=' ')
print()
def voisins(n, i,j) :
"""
retourne les couples de coordonnées des voisins de la cellule (i,j)
dans une matrice n sur n.
i est le numéro de ligne (entre 0 et n-1).
j est le numéro de colonne (entre 0 et n-1).
"""
voisinage = []
decale = (-1, 0, 1)
for l in decale :
for c in decale :
if (l, c) != (0, 0) :
v = (i+l, j+c)
if -1 < v[0] < n and -1 < v[1] < n : voisinage.append(v)
return voisinage
def composanteConnexe0A9(A, i, j ) :
coordonneesDesVoisins = voisins(len(A), i,j)
if A[i][j] == 0 :
A[i][j] = 9
for v in coordonneesDesVoisins :
composanteConnexe0A9(A, v[0], v[1])
n = 10
A = cree_matrice(n)
affiche_matrice(A)
composanteConnexe0A9(A, 0, 0 )
print()
affiche_matrice(A)
On obtient par exemple :
0 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 9 9 9 1 1 9 9 1 0 1 1 9 9 1 1 9 9 1 1 0 9 1 9 9 9 9 9 1 1 0 1 9 1 1 9 9 9 1 1 1 9 9 9 9 1 9 9 9 9 1 1 9 9 9 1 9 9 9 1 1 9 9 1 9 9 9 9 1 9 1 9 9 9 9 9 9 1 1 1 9 9 1 1 1 1 1 1 1 9 1 9 1 1 0 0 1 1 9 1 1
Une application : programmer un jeu de démineur. Le type de propagation vue ici peut intervenir lorsqu'on dévoile certaines cases sans mine et sans mine voisine.