Szczyty

Część sekcji Podstawy ścieżki C w Coddy. Lekcja 62 z 63.

Wyzwanie

Otrzymujesz dwuwymiarową siatkę wysokości całkowitych reprezentującą mapę terenu. Komórka jest nazywana szczytem, jeśli jej wartość jest ściśle większa od wartości wszystkich sąsiednich komórek (maksymalnie 8: na północy, południu, wschodzie, zachodzie oraz po przekątnych).

Zasady

8 sąsiadów: Musisz sprawdzić komórki na północy, południu, wschodzie, zachodzie oraz wszystkie cztery po przekątnych.
Komórki brzegowe: Jeśli komórka znajduje się na krawędzi lub w rogu, ma mniej niż 8 sąsiadów. Nadal jest szczytem, jeśli jej wartość jest ściśle większa od wartości wszystkich jej istniejących sąsiadów.
Ściśle większa: Jeśli sąsiednia komórka ma taką samą wysokość jak bieżąca komórka, bieżąca komórka nie jest szczytem.

Dane wejściowe

Dwie liczby całkowite N i M, oznaczające liczbę wierszy i kolumn.
Siatka liczb całkowitych o wymiarach N*M

Dane wyjściowe

Liczba całkowita oznaczająca łączną liczbę szczytów.
Współrzędne (wiersz i kolumna, indeksowane od 0) każdego szczytu, posortowane najpierw według wiersza, a następnie według kolumny.

Na przykład dla następujących danych wejściowych:

Dane wyjściowe:

Wyjaśnienie Szczyty znajdują się w następujących miejscach:

(0,4) o wysokości 4: Większa od wysokości sąsiadów (3, 1, 1).
(1,0) o wysokości 5: Większa od wysokości sąsiadów (1, 2, 1, 1, 1).
(2,2) o wysokości 9: Większa od wysokości wszystkich 8 otaczających ją komórek o wartości 1.
(4,1) o wysokości 3: Większa od wysokości sąsiadów (2, 1, 1, 1, 1).
(4,3) o wysokości 4: Większa od wysokości sąsiadów (1, 1, 1, 2, 1).

Spróbuj swoich sił

#include <stdio.h>

#define MAXN 100
#define MAXM 100

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

/**
 * Zwraca 1, jeśli komórka na pozycji (r, c) jest szczytem, w przeciwnym razie 0.
 * Szczyt musi mieć wartość ściśle większą od wartości wszystkich istniejących sąsiadów.
 */
int is_peak(int r, int c) {
    // TODO: Określ względne położenie 8 sąsiadów
    // (na północy, południu, wschodzie, zachodzie i na 4 przekątnych).
    
    // TODO: Przejdź przez wszystkich sąsiadów.
    // WAŻNA WSKAZÓWKA: Przed sprawdzeniem grid[nr][nc] MUSISZ się upewnić, 
    // że nr i nc mieszczą się w granicach (od 0 do N-1 oraz od 0 do M-1).
    
    return 1; // Wartość zastępcza
}

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

    // TODO: Wczytaj wartości siatki ze stdin za pomocą zagnieżdżonych pętli.
    
    // TODO: Przejdź przez każdą komórkę (i, j) siatki.
    // Jeśli is_peak(i, j) ma wartość true, zapisz współrzędne.
    // Możesz użyć dwóch tablic, takich jak peak_r[MAXN*MAXM] i peak_c[MAXN*MAXM] 
    // aby przechować wyniki przed ich wypisaniem.

    // TODO: Wypisz łączną liczbę szczytów.
    
    // TODO: Wypisz każdą zapisaną parę (row, col). 
    // Ponieważ przechodzisz najpierw po wierszach, a potem po kolumnach, będą już posortowane!

    return 0;
}

Wszystkie lekcje w sekcji Podstawy

1Wprowadzenie

Język C Witaj, świecie!Komentarze Podstawowa struktura programu

4Sterowanie przepływem

Instrukcja if If - else Else-if Instrukcja switch-case Operator warunkowy (ternary)Wyzwanie podsumowujące Zagnieżdżone if - else

7Funkcje

Deklarowanie funkcji Typy zwracane Parametry Powtórka – wyzwanie nr 1 Podstawy rekurencji Prototypy funkcji Powtórka – wyzwanie nr 2

Poćwicz samodzielnie: Kompilator C online