Quelques propositions d'élèves, et à la fin un corrigé du professeur.
À la suite de chaque proposition de code, un commentaire de correction du professeur. Le cartouche demandé en introduction a été supprimé ici.
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_chemin devrait renvoyer un booléen, pas 0 ou 1, 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.)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))
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"""
# 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))
""" auteur : Franck CHAMBON 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_connectés(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_connectés(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)
""" auteur : Franck CHAMBON 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 dépile(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_connectés(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_marqué = [[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_à_traiter = Pile() sommets_à_traiter.empile((0, 0)) est_marqué[0][0] = True nb_accessibles += 1 while not sommets_à_traiter.est_vide(): (i, j) = sommets_à_traiter.dépile() 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_connectés(i, j, idi, jdj): if not est_marqué[idi][jdj]: sommets_à_traiter.empile((idi, jdj)) est_marqué[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))