ピーク
CoddyのCジャーニー「基礎」セクションの一部。レッスン 62/63。
チャレンジ
地形図を表す、整数の標高が格納された2次元グリッドが与えられます。あるセルの値が隣接するすべてのセル(最大8つ:北、南、東、西、および4つの対角方向)よりも厳密に大きい場合、そのセルをピークと呼びます。
ルール
- 8つの隣接セル:北、南、東、西、および4つすべての対角方向を確認する必要があります。
- 境界上のセル:セルが端や角にある場合、隣接セルは8つ未満です。それでも、存在するすべての隣接セルより厳密に大きければ、ピークです。
- 厳密に大きい:隣接セルの標高が現在のセルと同じ場合、現在のセルはピークではありません。
入力
- 行数と列数を表す2つの整数
NとM。 N*M個の整数からなるグリッド
出力
- ピークの合計数を表す整数。
- 各ピークの座標(行と列、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オンラインコンパイラ