Exercices DFS et BFS

Les exercices à faire sont sur LeetCode.
Vous devez d'abord vous inscrire (Sign In). Vous pouvez pour cela vous connecter via Gmail, Github ou Facebook.

Si besoin, on pourra revoir et s'inspirer de l'algorithme de BFS (parcours en largeur) vu en cours.

Exercice

Plus court chemin dans une matrice 0 - 1
Vous devez changer le langage pour choisir Python3 au lieu de C++. Vous devez remplir le code de la fonction à droite (ici shortestPathBinaryMatrix).
Puis lisez l'énoncé à gauche.
Ici on vous donne une matrice (dont les éléments sont $0$ ou $1$), qui correspond à l'argument grid de la fonction shortestPathBinaryMatrix.
On vous demande de renvoyer le nombre minimum de cases de la matrice qu'il faut parcourir pour aller de la case en haut à gauche à la case en bas à droite.
Les exemples (en bas à gauche) peuvent aider à mieux comprendre :

Input: grid = [[0,1],[1,0]]
Output: 2

Signifie que si votre fonction shortestPathBinaryMatrix est appelé avec grid = [[0,1],[1,0]], il faut que votre fonction renvoie $2$.

Pour tester votre code, cliquer sur Run Code en bas à droite. Quand les tests marchent, vous pouvez cliquer sur Submit.

Pour vous aider, vous pouvez compléter le code suivant :

In [ ]:

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid) -> int:
        q = deque([(0, 0, 1)]) 
        # on met dans q des triplets (i, j, d) où (i, j) est une case de grid
        # et d est sa distance à la case en haut à gauche
        while q:
            i, j, d = q.popleft() # on parcourt la case ligne i, colonne j
            if ...: # tester si la grille vaut 0 en (i, j)
                if ...: # tester si (i, j) est en fait la case en bas à droite (l'arrivée)
                    return d
                
                # parcours des voisins de (i, j)
                for k in [-1, 0, 1]:
                    for l in [-1, 0, 1]:
                        # tester si (i + k, j + l) est une case de la grille (ne dépasse pas)
                        # si oui, on ajoute (i + k, j + l, d + 1) dans q
                        # et on marque (i + k, j + l) comme visité (en mettant 1 dans grid, par exemple)
        return -1 # si on ne trouve pas de chemin, on renvoie -1

from collections import deque class Solution: def shortestPathBinaryMatrix(self, grid) -> int: q = deque([(0, 0, 1)]) # on met dans q des triplets (i, j, d) où (i, j) est une case de grid # et d est sa distance à la case en haut à gauche while q: i, j, d = q.popleft() # on parcourt la case ligne i, colonne j if ...: # tester si la grille vaut 0 en (i, j) if ...: # tester si (i, j) est en fait la case en bas à droite (l'arrivée) return d # parcours des voisins de (i, j) for k in [-1, 0, 1]: for l in [-1, 0, 1]: # tester si (i + k, j + l) est une case de la grille (ne dépasse pas) # si oui, on ajoute (i + k, j + l, d + 1) dans q # et on marque (i + k, j + l) comme visité (en mettant 1 dans grid, par exemple) return -1 # si on ne trouve pas de chemin, on renvoie -1

Solution

In [ ]:

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid) -> int:
        q = deque([(0, 0, 1)]) 
        # on met dans q des triplets (i, j, d) où (i, j) est une case de grid
        # et d est sa distance à la case en haut à gauche
        n = len(grid)
        while q:
            i, j, d = q.popleft()
            if grid[i][j] == 0:
                if (i, j) == (n - 1, n - 1): # on a trouvé l'arrivée
                    return d
                for k in [-1, 0, 1]:
                    for l in [-1, 0, 1]:
                        if 0 <= i + k < n and 0 <= j + l < n:
                            q.append((i + k, j + l, d + 1))
                            grid[i][j] = 1
        return -1

from collections import deque class Solution: def shortestPathBinaryMatrix(self, grid) -> int: q = deque([(0, 0, 1)]) # on met dans q des triplets (i, j, d) où (i, j) est une case de grid # et d est sa distance à la case en haut à gauche n = len(grid) while q: i, j, d = q.popleft() if grid[i][j] == 0: if (i, j) == (n - 1, n - 1): # on a trouvé l'arrivée return d for k in [-1, 0, 1]: for l in [-1, 0, 1]: if 0 <= i + k < n and 0 <= j + l < n: q.append((i + k, j + l, d + 1)) grid[i][j] = 1 return -1

Exercice

Nombre d'îles
Il s'agit de trouver le nombre de composante connexes d'un graphe (avec DFS ou BFS).
Pour vous aider, vous pouvez compléter le code suivant :

In [3]:

class Solution:
    def numIslands(self, grid) -> int:
        n, p = ... # dimensions de la matrice
        visited = ... # création d'une matrice n*p remplie de False
        def dfs(i, j): # fait un parcourir en profondeur depuis la case (i, j)
            # marquer (i, j) comme étant visité
            for (k, l) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                # pour tous les voisins possibles de (i, j)
                if ...: # si (k, l) ne sort pas de la matrice, est de la terre et n'a pas été visité
                    dfs(k, l) # visiter (k, l)
        # appeler dfs(i, j) pour chaque case non encore visité et contenant de la terre
        # renvoyer le nombre d' appels à dfs

class Solution: def numIslands(self, grid) -> int: n, p = ... # dimensions de la matrice visited = ... # création d'une matrice n*p remplie de False def dfs(i, j): # fait un parcourir en profondeur depuis la case (i, j) # marquer (i, j) comme étant visité for (k, l) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: # pour tous les voisins possibles de (i, j) if ...: # si (k, l) ne sort pas de la matrice, est de la terre et n'a pas été visité dfs(k, l) # visiter (k, l) # appeler dfs(i, j) pour chaque case non encore visité et contenant de la terre # renvoyer le nombre d' appels à dfs

Solution

In [5]:

class Solution:
    def numIslands(self, grid) -> int:
        n, p = len(grid), len(grid[0])
        visited = [[False]*p for _ in range(n)]
        def dfs(i, j):
            visited[i][j] = True
            for (k, l) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if 0 <= k < n and 0 <= l < p and not visited[k][l] and grid[k][l] == "1":
                    dfs(k, l)
        r = 0
        for i in range(n):
            for j in range(p):
                if not visited[i][j] and grid[i][j] == "1":
                    dfs(i, j)
                    r += 1
        return r

class Solution: def numIslands(self, grid) -> int: n, p = len(grid), len(grid[0]) visited = [[False]*p for _ in range(n)] def dfs(i, j): visited[i][j] = True for (k, l) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: if 0 <= k < n and 0 <= l < p and not visited[k][l] and grid[k][l] == "1": dfs(k, l) r = 0 for i in range(n): for j in range(p): if not visited[i][j] and grid[i][j] == "1": dfs(i, j) r += 1 return r

Exercice

Carrés parfaits

Vous pouvez utiliser un BFS où les sommets sont des entiers et où il y a une arête d'un entier $n$ à un entier $p$ si $n - p$ est un carré parfait.
Il faut alors chercher la distance de $n$ à $0$.
Remarque : Il n'est pas nécessaire de construire le graphe en entier. On ne calcule les voisins d'un entier qu'au moment où on en a besoin.