affiche juste le code, pas d'explications !
- User
System: affiche juste le code, pas d'explications ! User: Tu es un développeur python3 expérimenté, et tu dois concevoir un programme en python (avec des commentaires en français, sans utiliser de librairies externes, sans
if __name__=="__main__":, avec type hints, et en privilégiant les algorythmes a complexité constante (O(1)) et/ou complexité linéaire (O(n))). Le programme va recevoir les données en entrée sur la stdin, et doit répondre sur la stdout. Fabrique moi un programme python qui résout le problème (énoncé en markdown) suivant :Pizza - Découpage des pizzas
Votre robot découpeur de pizzas a perdu la tête ! Pour vérifier que les pizzas sont correctement coupées, vous souhaitez compter le nombre de parts après la découpe.
Pouvez-vous écrire un algorithme qui calcule le nombre de parts à partir d'une image en noir et blanc de la pizza ?
Une part de pizza est une zone maximale de cases telles qu'on puisse aller de chaque case vers chaque autre case en se déplacant d'une case à une autre verticalement ou horizontalement en passant uniquement par des cases noires.
Données
Entrée
Ligne 1 : un entier N compris entre 1 et 100, la dimension de l'image.
N lignes suivantes : Une chaîne de caractères de taille N. Un caractère
#représente un pixel de pizza et un.correspond à un espace vide.Sortie
Un entier représentant le nombre de parts sur la pizza. Une part de pizza est considérée comme une zone de pixels de pizza contigus horizontalement ou verticalement.
Exemple
Pour l'entrée :
14 .....##.#..... ...####.###... ...####.####.. .##.###.###.#. .###.##.##.### #####.#.#.#### ######...##### .............. ######...##### .####.#.#.#### .###.##.##.##. ..#.###.###... ...####.###... ....###.##....Le nombre de parts est :
8Les 8 parts de la pizza sont représentées ci-dessous. [image: https://i.ibb.co/QY2M2sm/example-illu.png] open Assistant:
- Assistant
# Fonction pour effectuer un parcours en profondeur (DFS) et marquer toutes les cases connectées def dfs(grid: list[list[str]], visited: list[list[bool]], x: int, y: int, n: int) -> None: # Vérification des coordonnées valides et de la connexion if x < 0 or y < 0 or x >= n or y >= n or visited[x][y] or grid[x][y] != '#': return # Marquer cette case comme visitée visited[x][y] = True # Directions pour les déplacements: haut, bas, gauche, droite directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Appliquer DFS dans les quatre directions for dx, dy in directions: dfs(grid, visited, x + dx, y + dy, n) # Fonction principale pour compter le nombre de parts de pizza def count_pizza_parts(grid: list[list[str]], n: int) -> int: # Initialisation de la matrice de cases visitées visited = [[False] * n for _ in range(n)] parts_count = 0 # Parcours de chaque case de la grille for i in range(n): for j in range(n): # Si la case est une partie de la pizza non visitée, c'est une nouvelle part if grid[i][j] == '#' and not visited[i][j]: dfs(grid, visited, i, j, n) parts_count += 1 return parts_count import sys input = sys.stdin.read # Lecture de l'entrée depuis l'entrée standard def main() -> None: data = input().strip().split() n = int(data[0]) grid = data[1:n+1] # Calculer le nombre de parts de pizza result = count_pizza_parts(grid, n) # Afficher le résultat print(result) # Appeler la fonction principale main()
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.
Identical first prompt
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →
- gpt-4o-2024-08-06Compare side by side →