Pics

Fait partie de la section Fundamentals du Journey C de Coddy — leçon 62 sur 63.

Défi

On vous donne une grille 2D d'élévations entières représentant une carte de terrain. Une cellule est appelée un pic si sa valeur est strictement supérieure à tous ses voisins adjacents (jusqu'à 8 : nord, sud, est, ouest et les quatre diagonales).

Règles

8 Voisins : Vous devez vérifier le nord, le sud, l'est, l'ouest et les quatre diagonales.
Cellules de bordure : Si une cellule se trouve sur un bord ou un coin, elle a moins de 8 voisins. Elle est toujours considérée comme un pic si elle est strictement supérieure à tous ses voisins existants.
Strictement supérieur : Si un voisin a la même élévation que la cellule actuelle, la cellule actuelle n'est pas un pic.

Entrée

Deux entiers N et M représentant les lignes et les colonnes.
Une grille N*M d'entiers

Sortie

Un entier représentant le nombre total de pics.
Les coordonnées (ligne et colonne, indexées à partir de 0) de chaque pic, triées d'abord par ligne puis par colonne.

Par exemple pour cette entrée :

Voici la sortie :

Explication Les pics se trouvent aux emplacements suivants :

(0,4) avec une élévation de 4 : Supérieure aux voisins (3, 1, 1).
(1,0) avec une élévation de 5 : Supérieure aux voisins (1, 2, 1, 1, 1).
(2,2) avec une élévation de 9 : Supérieure aux 8 voisins environnants de valeur 1.
(4,1) avec une élévation de 3 : Supérieure aux voisins (2, 1, 1, 1, 1).
(4,3) avec une élévation de 4 : Supérieure aux voisins (1, 1, 1, 2, 1).

Essayez vous-même

#include <stdio.h>

#define MAXN 100
#define MAXM 100

int N, M;
int grid[MAXN][MAXM];

/**
 * Retourne 1 si la cellule à (r, c) est un sommet, 0 sinon.
 * Un sommet doit être strictement supérieur à tous ses voisins existants.
 */
int is_peak(int r, int c) {
    // TODO: Définir les positions relatives des 8 voisins
    // (Nord, Sud, Est, Ouest, et les 4 diagonales).
    
    // TODO: Parcourir chaque voisin.
    // CONSEIL CRITIQUE : Avant de vérifier grid[nr][nc], vous DEVEZ vous assurer 
    // que nr et nc sont dans les limites (0 à N-1 et 0 à M-1).
    
    return 1; // Espace réservé
}

int main() {
    // Lire les dimensions
    if (scanf("%d %d", &N, &M) != 2) {
        return 1;
    }

    // TODO: Lire les valeurs de la grille depuis stdin en utilisant des boucles imbriquées.
    
    // TODO: Itérer sur chaque cellule (i, j) de la grille.
    // Si is_peak(i, j) est vrai, stocker les coordonnées.
    // Vous pouvez utiliser deux tableaux comme peak_r[MAXN*MAXM] et peak_c[MAXN*MAXM] 
    // pour stocker les résultats avant l'affichage.

    // TODO: Afficher le nombre total de sommets.
    
    // TODO: Afficher chaque paire (ligne, col) stockée. 
    // Puisque vous itérez par ligne puis par colonne, elles seront déjà triées !

    return 0;
}

Toutes les leçons de Fundamentals

1Introduction

Langage C Hello World !Commentaires Structure de base d'un programme

4Structures de contrôle

L'instruction If If - Else Else-If Switch Case Opérateur ternaire Défi récapitulatif If - Else imbriqués

7Fonctions

Déclarer une fonction Types de retour Paramètres Défi récapitulatif n°1 Bases de la récursivité Prototypes de fonction Défi récapitulatif n°2