Q1 - Cases inaccessibles⚓︎
Le problème
Proposition 1⚓︎
🐍 Script Python
def nb_cases_inaccessibles(nb_lignes: int, nb_colonnes: int, cases: list) -> int:
"""
Recherche et renvoie le nombre de case inaccesible
"""
# 4 directions possibles
directions = [(1, 0),(0,1),(-1,0),(0,-1)]
def est_possible(y:int, x:int) -> bool:
""" Regarde si le déplacement est possible
"""
return (0 <= y < nb_lignes) and (0 <= x < nb_colonnes)
def recherche_chemin(y:int, x:int, direction_y:int, direction_x:int) -> int:
""" Recherche et renvoie 1 si on peut prendre le chemin sinon 0
"""
déplacement_y = y + direction_y
déplacement_x = x + direction_x
if not(est_possible(déplacement_y, déplacement_x)) and (cases[y][x] < cases[déplacement_y][déplacement_x]):
return 0
return 1
départ = (0,0)
def nombre_pas(départ:tuple) -> int:
""" Renvoie le nombre de case visité de manière récursive """
# Fonctionne théoriquement mais pas à la pratique car il y a sois disant trop de récursion
nb_pas = 0
y,x = départ
for direction_y, direction_x in directions:
if recherche_chemin(y,x,direction_y,direction_x) != 0:
déplacement_x = x + direction_x
déplacement_y = y + direction_y
nb_pas += 1 + nombre_pas((déplacement_y,déplacement_x))
return nb_pas
return nombre_pas(départ)
# tests
import doctest
doctest.testmod()
# Entrée
nb_lignes, nb_colonnes = map(int, input().split())
cases = [list(map(int, input().split())) for _ in range(nb_lignes)]
# Sortie
nombre_cases = nb_lignes * nb_colonnes
print(nombre_cases - nb_cases_inaccessibles(nb_lignes, nb_colonnes, cases))
recherche_chemindevrait renvoyer un booléen, pas0ou1, ce style de code est ici d'un codeur en C. (Ce n'est pas que c'est mal, mais soit on code en C, soit en Python, et si on se fait aider, on remobilise intelligemment le matériel.)- L'algorithme n'est pas efficace, il faut mémoriser les cases déjà visitées. Il tourne en boucle infinie...
Proposition 2⚓︎
🐍 Script Python
from collections import deque
# Entrée
nb_lignes, nb_colonnes = map(int, input().split())
cases = [list(map(int, input().split())) for _ in range(nb_lignes)]
dictionnaire_vecteurs = {"N": (-1, 0), "S": (1, 0), "O": (0, -1), "E": (0, 1)}
#J'utilise une `deque` comme implémentation de la file (celle-ci est plus efficace et plus rapide qu'une classe `File` en P.O.O)
file = deque()
enfile = file.append
défile = file.popleft
def est_dans_la_liste(x: int, y: int) -> bool:
"""
Permet de renvoyer True si les coordonnées `x` et `y` sont dans le domaine de
définition de la liste `cases`
>>> cases = [[1, 6, 3], [5, 9, 6], [7, 2, 0], [5, 4, 6]]
>>> est_dans_la_liste(1,2)
True
>>> est_dans_la_liste(9, 5)
False
"""
return ((0 <= x < nb_lignes) and (0 <= y < nb_colonnes))
def est_déplaçable(élément: int, x: int, y: int) -> bool:
"""
Permet de renvoyer True si la valeur situé aux coordonnées (`x`,`y`) est inférieure ou égale
à `élément`
>>> cases = [[1, 6, 3], [5, 9, 6], [7, 2, 0], [5, 4, 6]]
>>> est_déplaçable(cases[0][1], 0, 2)
True
>>> est_déplaçable(cases[0][0], 0, 1)
False
"""
return cases[x][y] <= élément
def donne_les_directions(x: int, y: int) -> list:
"""
Renvoie la liste des directions où on peut se déplacer à partir des coordonnées(`x`, `y`)
>>> cases = [[1, 6, 3], [5, 9, 6], [7, 2, 0], [5, 4, 6]]
>>> donne_les_directions(0, 0)
['S']
>>> donne_les_directions(2, 1)
['S', 'E']
"""
liste_directions = []
for direction, tuple_delta in dictionnaire_vecteurs.items():
delta_x, delta_y = tuple_delta
x_temporaire = x + delta_x
y_temporaire = y + delta_y
if est_dans_la_liste(x_temporaire, y_temporaire):
if est_déplaçable(cases[x][y],x_temporaire, y_temporaire):
liste_directions.append(direction)
return liste_directions
def donne_nb_cases_inaccessibles(x_départ: int, y_départ: int) -> int:
"""
Cette fonction est le coeur du programme.
Elle a pour paramètres des coordonnées (`x_départ`,`y_départ`) qui sont les coordonnées
de départ du chemin dans `cases`
Et elle renvoie le nombre de cases inaccessible
>>> cases = [[4, 5, 3], [3, 2, 6], [4, 1, 1], [0, 1, 2]]
>>> donne_nb_cases_inaccessibles(0,0)
5
"""
déja_vu = set()
enfile((x_départ, y_départ))
while len(file) != 0:
x, y = défile()
déja_vu.add((x, y))
liste_directions = donne_les_directions(x, y)
for direction in liste_directions:
delta_x, delta_y = dictionnaire_vecteurs[direction]
x_temp = x + delta_x
y_temp = y + delta_y
if (x_temp, y_temp) in déja_vu:
pass
else:
enfile((x_temp, y_temp))
return (nb_lignes*nb_colonnes) - len(déja_vu)
# tests
import doctest
doctest.testmod()
# Sortie
print(donne_nb_cases_inaccessibles(0, 0))
- Bravo, très bien.
- Aérer les doctest.
Proposition 3⚓︎
🐍 Script Python
def parcour_plateau(matrice, nb_ligne: int, nb_cologne: int):
""" on parcour la matrice qui fait référence à
un plateau de jeu et on doit atteindre la dernier partie de la matrice
de plus on conte les casse qui sont inaccesible
>>> matrice = [['4', '5', '3'], ['3', '2', '6'], ['4', '1', '1'], ['0', '1', '2']]
5
>>> matrice = [['4', '5', '3'], ['5', '2', '6'], ['4', '1', '1'], ['0', '1', '2']]
2
"""
aller_droite = 0
aller_bad = 0
nb_inaccesible = 0
while aller_droite < nb_cologne - 1 and aller_bad < nb_ligne - 1:
if aller_droite < nb_cologne - 1:
if matrice[aller_bad][aller_droite] < matrice[aller_bad][aller_droite + 1]:
nb_inaccesible += 1
else:
if matrice[aller_bad][aller_droite] < matrice[aller_bad + 1][aller_droite]:
nb_inaccesible += 1
aller_droite += 1
else:
aller_droite += 1
if aller_bad < nb_ligne - 1:
if matrice[aller_bad][aller_droite] < matrice[aller_bad + 1][aller_droite]:
nb_inaccesible += 1
else:
if matrice[aller_bad][aller_droite] < matrice[aller_bad][aller_droite + 1]:
nb_inaccesible += 1
aller_bad += 1
else:
aller_bad += 1
return nb_inaccesible
nb_ligne, nb_cologne = map(int, input().split())
matrice = [[[] for _ in range(nb_cologne)] for _ in range(nb_ligne)]
for x in range (nb_ligne):
matrice[x] = input().split()
print(parcour_plateau(matrice, nb_ligne, nb_cologne))
"""problème il est trop long"""
- Le code est très peu clair, on ne comprend pas ce que fait le code.
- Ce n'est pas la bonne méthode pour le résoudre.
Proposition 4⚓︎
🐍 Script Python
# 0- Coeur du programme
def est_dans_le_tableau(nb_lignes: int, nb_colonnes: int, i: int, j: int) -> bool:
""" Renvoie True si le curseur i,j est dans le tableau
>>> est_dans_le_tableau(4, 3, 0, 0)
True
>>> est_dans_le_tableau(10, 10, 10, 10)
False
"""
if 0 <= i < nb_lignes and 0 <= j < nb_colonnes:
return True
else:
return False
def déterminer_accessibilité(nb_lignes: int, nb_colonnes: int, tableau:list, est_accessible: list, i: int, j: int) -> list:
""" Fonction récursive renvoyant est_accessible, la liste des cases accessibles ou non du tableau.
>>> tableau = [[4,5,3], [3,2,6], [4,1,1], [0,1,2]]
>>> est_accessible = [[False, False, False], [False, False, False], [False, False, False], [False, False, False]]
>>> déterminer_accessibilité(4, 3, tableau, est_accessible, 0, 0)
[[True, False, False], [True, True, False], [False, True, True], [True, True, False]]
"""
est_accessible[i][j] = True
# Chaque combinaison correspond à une direction à tester, dans l'ordre on a :
# Droite, Gauche, Bas , Haut
combinaisons = [(0,1), (0,-1), (1,0), (-1,0)]
for x,y in combinaisons: # Pour chaque combinaisons,
if est_dans_le_tableau(nb_lignes, nb_colonnes, i+x, j+y) : # - On vérifie si le point se trouve dans le tableau
if tableau[i+x][j+y] <= tableau[i][j]: # - Que le tableau de ce point soit plus petit que le précedent
if est_accessible[i+x][j+y] == False : # - Que l'on est pas déjà passé par ce point (on évite de boucler)
est_accessible = déterminer_accessibilité(nb_lignes, nb_colonnes, tableau, est_accessible, i+x, j+y)
return est_accessible
def nb_cases_inaccessibles(nb_lignes: int, nb_colonnes: int, tableau: list) -> int:
"""Renvoie le nombre de cases inaccessibles
>>> nb_cases_inaccessibles(2, 2, [[1,2], [1,0]])
1
>>> nb_cases_inaccessibles(4, 3, [[4,5,3], [3,2,6], [4,1,1], [0,1,2]])
5
"""
est_accessible = [[False for _ in range(nb_colonnes)] for _ in range(nb_lignes)]
déterminer_accessibilité(nb_lignes, nb_colonnes, tableau, est_accessible, 0, 0)
compteur = 0
for ligne in est_accessible:
for x in ligne:
if x is False:
compteur += 1
return compteur
# 1- Tests
import doctest
doctest.testmod()
# 2- Lecture des entrées
import sys
nb_lignes, nb_colonnes = map(int,input().split())
sys.setrecursionlimit(1000000)
# 3- Appel de la fonction / Sortie
tableau = [list(map(int,input().split())) for _ in range(nb_lignes)]
print(nb_cases_inaccessibles(nb_lignes, nb_colonnes, tableau))
- On ne comprend pas bien comment la récursivité s'arrête...
- Sinon, c'est bien !!!
Corrigé du professeur⚓︎
Parcours récursif⚓︎
🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2003/qualification/cases_inaccessibles
"""
nb_lignes, nb_colonnes = map(int, input().split())
grille = [list(map(int, input().split())) for i in range(nb_lignes)]
vu = [[False for _ in range(nb_colonnes)] for _ in range(nb_lignes)]
def est_valide(i: int, j: int) -> bool:
"""Renvoie la réponse : (i, j) est-elle une position valide sur la grille ?
"""
return (0 <= i < nb_lignes) and (0 <= j < nb_colonnes)
def sont_connectes(i: int, j: int, idi: int, jdj: int) -> bool:
"""Renvoie la réponse : Peut-on se déplacer de (i, j) vers (idi, jdj) ?
"""
return grille[idi][jdj] <= grille[i][j]
def visite(i: int, j: int) -> None:
"""Visite récursivement le graphe"""
if vu[i][j] == False:
vu[i][j] = True
for (di, dj) in [(0, +1), (0, -1), (+1, 0), (-1, 0)]:
idi, jdj = i + di, j + dj
if est_valide(idi, jdj) and sont_connectes(i, j, idi, jdj):
visite(idi, jdj)
visite(0, 0)
nb_inaccessibles = 0
for i in range(nb_lignes):
for j in range(nb_colonnes):
if vu[i][j] == False:
nb_inaccessibles += 1
print(nb_inaccessibles)
Parcours itératif⚓︎
🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2003/qualification/cases_inaccessibles
"""
class Pile:
def __init__(self):
self.pile = []
def est_vide(self):
return self.pile == []
def empile(self, x):
self.pile.append(x)
def depile(self):
if self.est_vide():
raise ValueError("Pile vide")
else:
return self.pile.pop()
def nb_inaccessibles(grille: list[list[int]]) -> int:
"""Renvoie le nombre de cases inaccessibles.
* On part en haut à gauche.
* On bouge 1 case horizontalement ou verticalement,
+ si la valeur est inférieure ou égale.
* Exemple : 5, 3, 6, 4 et 2 sont inaccessibles.
>>> ligne_1 = [4, 5, 3]
>>> ligne_2 = [3, 2, 6]
>>> ligne_3 = [4, 1, 1]
>>> ligne_4 = [0, 1, 2]
>>> nb_inaccessibles([ligne_1, ligne_2, ligne_3, ligne_4])
5
"""
nb_lignes = len(grille)
nb_colonnes = len(grille[0])
def est_valide(i: int, j: int) -> bool:
"""Renvoie la réponse : (i, j) est-elle une position valide sur la grille ?
"""
return (0 <= i < nb_lignes) and (0 <= j < nb_colonnes)
def sont_connectes(i: int, j: int, idi: int, jdj: int) -> bool:
"""Renvoie la réponse : Peut-on se déplacer de (i, j) vers (idi, jdj) ?
"""
return grille[idi][jdj] <= grille[i][j]
est_marque = [[False for j in range(nb_colonnes)] for i in range(nb_lignes)]
# est_marqué est une matrice de booléen, indiquant si la case (i, j) a été visitée, ou programmée.
nb_accessibles = 0
sommets_a_traiter = Pile()
sommets_a_traiter.empile((0, 0))
est_marque[0][0] = True
nb_accessibles += 1
while not sommets_a_traiter.est_vide():
(i, j) = sommets_a_traiter.depile()
for (di, dj) in [(0, +1), (0, -1), (+1, 0), (-1, 0)]:
idi, jdj = i + di, j + dj
if est_valide(idi, jdj) and sont_connectes(i, j, idi, jdj):
if not est_marque[idi][jdj]:
sommets_a_traiter.empile((idi, jdj))
est_marque[idi][jdj] = True
nb_accessibles += 1
return nb_lignes * nb_colonnes - nb_accessibles
import doctest
doctest.testmod()
nb_lignes, nb_colonnes = map(int, input().split())
grille = [list(map(int, input().split())) for i in range(nb_lignes)]
print(nb_inaccessibles(grille))