Menu
CoddyTech

ピーク

CoddyのCジャーニー「基礎」セクションの一部。レッスン 62/63。

challenge icon

チャレンジ

地形図を表す、整数の標高が格納された2次元グリッドが与えられます。あるセルの値が隣接するすべてのセル(最大8つ:北、南、東、西、および4つの対角方向)よりも厳密に大きい場合、そのセルをピークと呼びます。 

ルール

  • 8つの隣接セル:北、南、東、西、および4つすべての対角方向を確認する必要があります。
  • 境界上のセル:セルが端や角にある場合、隣接セルは8つ未満です。それでも、存在するすべての隣接セルより厳密に大きければ、ピークです。
  • 厳密に大きい:隣接セルの標高が現在のセルと同じ場合、現在のセルはピークではありません。

入力

  • 行数と列数を表す2つの整数 N と M。
  • N*M 個の整数からなるグリッド

出力

  1. ピークの合計数を表す整数。
  2. 各ピークの座標(行と列、0始まり)。行、次に列の順に並べます。

たとえば、次の入力の場合:

5 5
1 2 1 3 4
5 1 1 1 1
1 1 9 1 1
2 1 1 1 2
1 3 1 4 1

出力は次のとおりです:

5
0 4
1 0
2 2
4 1
4 3

説明 ピークは次の位置にあります:

  • (0,4)、標高4:隣接セル(3、1、1)より大きい。
  • (1,0)、標高5:隣接セル(1、2、1、1、1)より大きい。
  • (2,2)、標高9:周囲の8つの1すべてより大きい。
  • (4,1)、標高3:隣接セル(2、1、1、1、1)より大きい。
  • (4,3)、標高4:隣接セル(1、1、1、2、1)より大きい。

自分で試してみよう

#include <stdio.h>

#define MAXN 100
#define MAXM 100

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

/**
 * (r, c) のセルがピークなら 1、それ以外なら 0 を返す。
 * ピークは、存在するすべての隣接セルよりも大きい値でなければならない。
 */
int is_peak(int r, int c) {
    // TODO: 8 つの隣接セルの相対位置を定義する
    // (北、南、東、西、および斜め 4 方向)。
    
    // TODO: 各隣接セルを順に調べる。
    // 重要なヒント: grid[nr][nc] を調べる前に、必ず 
    // nr と nc が範囲内(0 から N-1、および 0 から M-1)にあることを確認する。
    
    return 1; // 仮の実装
}

int main() {
    // 行数と列数を読み取る
    if (scanf("%d %d", &N, &M) != 2) {
        return 1;
    }

    // TODO: ネストしたループを使って stdin からグリッドの値を読み取る。
    
    // TODO: グリッド内のすべてのセル (i, j) を順に調べる。
    // is_peak(i, j) が真なら、その座標を保存する。
    // peak_r[MAXN*MAXM] と peak_c[MAXN*MAXM] のような 2 つの配列を使える 
    // 出力する前に結果を保存するために。

    // TODO: ピークの総数を出力する。
    
    // TODO: 保存した各 (row, col) の組を出力する。 
    // 行、列の順に走査するので、すでに整列されています!

    return 0;
}

基礎のすべてのレッスン

自分で練習してみよう: Cオンラインコンパイラ