農場有許多山丘,Farmer John 想在上面安排守衛,保護他珍貴的乳牛。
若每個山頂都放一個守衛,他想知道需要多少人。他有一張整數矩陣地圖,有 $N$ 行 $(1 \lt N \le 700)$ 和 $M$ 列 $(1 \lt M \le 700)$。每個元素是海拔 $H_{ij}$ $(0 \le H_{ij} \le 10,000)$。請幫他確定地圖上的山頂數量。
山頂由一個或多個相鄰且值相同的矩陣元素組成,其周圍只能是地圖邊緣或海拔更低的元素。兩個不同元素相鄰,當且僅當它們的 $X$ 座標之差的絕對值不超過 1,且 $Y$ 座標之差的絕對值也不超過 1。
輸入格式
- 第 1 行:兩個空格分隔的整數 $N$ 和 $M$。
- 第 $2,\ldots,N+1$ 行:第 $i+1$ 行以 $M$ 個空格分隔的整數 $H_{ij}$ 描述矩陣的第 $i$ 行。
輸出格式
- 第 1 行:一個整數,表示山頂數量。
範例
輸入格式 1
8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 1 1 2 1 0
輸出格式 1
3
說明
共有三個山頂:左上角高度為 4 的點、底部某個高度為 2 的點,以及右上角某個高度為 1 的點。
題目作者:Fatih Gelgi,2008