第16回日本情報オリンピック　予選５

2016年12月11日
情報オリンピック日本委員会

問題

JOI カルデラは景観の良さが多くの登山家に愛される美しい地形である． 特に，尾根と呼ばれる場所からの景観は絶景である．

JOI カルデラの土地は南北 H キロメートル，東西 W キロメートルの長方形である． 南北，東西に 1 キロメートルごとに JOI カルデラの土地を分け，これら H×W 個の領域を区域と呼ぶ． すべての区域において，その中では標高は等しい．また，異なる区域の標高は異なる．

ある区域に雨が降ると，雨水はその区域に東西南北に隣り合う最大で 4 つの区域のうち， 標高がその区域より低いような区域のすべてに流れる．そのような区域がない場合，雨水はその区域に溜まる． 他の区域から流れてきた雨水についても同様である． JOI カルデラの外側は，外輪山の急峻な崖に囲まれているため，雨水が JOI カルデラの外に流れ出すことはない．

ある区域について，その区域のみに雨が降った場合，最終的に複数の区域に雨水が溜まるとき，その区域を尾根と呼ぶ． 絶景をこよなく愛する登山家たちのために，尾根の区域がいくつあるかを求めるプログラムを作成せよ．

入力

入力は 1 + H 行からなる．

1 行目には 2 個の整数 H, W (1 ≦ H ≦ 1000, 1 ≦ W ≦ 1000) が空白を区切りとして書かれており，JOI カルデラが南北に H キロメートル，東西に W キロメートルにわたることを表す．

続く H 行にはそれぞれ W 個の整数が空白を区切りとして書かれており，標高の情報を表す． H 行のうちの i 行目の j 番目 (1 ≦ i ≦ H, 1 ≦ j ≦ W) の整数 M_i,j (1 ≦ M_i,j ≦ H×W) は，JOI カルデラの北から i 行目，西から j 列目の区域の標高を表す． (i,j) ≠ (k,l) なら，M_i,j ≠ M_k,l を満たす．

出力

尾根の区域の個数を 1 行で出力せよ．

入出力例

3 3
2 9 4
7 5 3
6 1 8
  

3 5
5 3 8 2 14
9 10 4 1 13
12 7 11 6 15
  

4
   

4
  

入力例 1 において，標高が 5, 7, 8, 9 の 4 個の区域が尾根である．例えば，標高 9 の区域に雨が降った場合，最終的に雨水は標高 1, 2, 3 の 3 個の区域に溜まる．したがって，標高 9 の区域は尾根である．また，標高 6 の区域に雨が降った場合，最終的に雨水は標高 1 の区域にしか溜まらない．したがって，標高 6 の区域は尾根ではない．

入力例 2 において，標高が 8, 10, 11, 12 の 4 個の区域が尾根である．

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．

採点用データ