2365 問(wèn)題 Z: 信息學(xué)奧賽一本通T1454-山峰和山谷
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 73 解決: 60
題目描述
給定一個(gè) n×n 的網(wǎng)格狀地圖，每個(gè)方格 (i,j)有一個(gè)高度 wij 。如果兩個(gè)方格有公共頂點(diǎn)，則它們是相鄰的。
定義山峰和山谷如下：
均由地圖上的一個(gè)連通塊組成；
所有方格高度都相同；
周圍的方格（即不屬于山峰或山谷但與山峰或山谷相鄰的格子）高度均大于山谷的高度，或小于山峰的高度。
求地圖內(nèi)山峰和山谷的數(shù)量。特別地，如果整個(gè)地圖方格的高度均相同，則整個(gè)地圖既是一個(gè)山谷，也是一個(gè)山峰。
輸入
第一行一個(gè)整數(shù)n（2≤n≤1000），表示地圖的大小。
接下來(lái) n 行每行 n 個(gè)整數(shù)表示地圖。第 i 行有 n 個(gè)整數(shù) wi1,wi2,…,win(0≤wij≤1000000000)，表示地圖第 i 行格子的高度。
輸出
輸出一行兩個(gè)整數(shù)，分別表示山峰和山谷的數(shù)量。
樣例輸入
5 8 8 8 7 7 7 7 8 8 7 7 7 7 7 7 7 8 8 7 8 7 8 8 8 8
樣例輸出
2 1
提示
樣例1解釋：
樣例輸入2:：
5 5 7 8 3 1 5 5 7 6 6 6 6 6 2 8 5 7 2 5 8 7 1 0 1 7樣例輸出2:
3 3樣例2解釋：
比賽公告
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈