[HOJ 297][NOIP 2010 提高組]引水入城 (題目備份)

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 297 - 引水入城

Problem Statistics

Solved Member: 14　　Submission: 148　　User Tried: 14

Problem：

在一個遙遠的國度，一側是風景秀美的湖泊，另一側則是漫無邊際的沙漠。該國的行政區劃十分特殊，剛好構成一個N 行M 列的矩形，如上圖所示，其中每個格子都代表一座城市，每座城市都有一個海拔高度。

為了使居民們都盡可能飲用到清澈的湖水，現在要在某些城市建造水利設施。水利設施有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。因此，只有與湖泊毗鄰的第1行的城市可以建造蓄水廠。而輸水站的功能則是通過輸水管線利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是存在比它海拔更高且擁有公共邊的相鄰城市，已經建有水利設施。

由於第N 行的城市靠近沙漠，是該國的干旱區，所以要求其中的每座城市都建有水利設施。

簡單的說你要在第一行選最少個城市建立蓄水廠，使得第N行的每個城市都能獲得水資源，當水資源能從城市A流往城市B，僅當城市A與城市B相鄰(上下左右)，且城市A的海拔高度大於城市B的海拔高度。

那麼，這個要求能否滿足呢？如果能，請計算最少建造幾個蓄水廠；如果不能，求乾旱區中不可能建有水利設施的城市數目。

Input：

輸入的第一行是兩個正整數N 和M，表示矩形的規模。

接下來N 行，每行M 個正整數，依次代表每座城市的海拔高度。

測試資料編號	能否滿足要求	N	M
1	不能	≤ 10	≤ 10
2	不能	≤ 100	≤ 100
3	不能	≤ 500	≤ 500
4	能	= 1	≤ 10
5	能	≤ 10	≤ 10
6	能	≤ 100	≤ 20
7	能	≤ 100	≤ 50
8	能	≤ 100	≤ 100
9	能	≤ 200	≤ 200
10	能	≤ 500	≤ 500

Output：

輸出有兩行。

如果能滿足要求，輸出的第一行是整數1，第二行是一個整數，代表最少建造幾個蓄水廠。

如果不能滿足要求，輸出的第一行是整數0，第二行是一個整數，代表有幾座乾旱區中的城市不可能建有水利設施。

Sample Input：

Sample #1:
2 5
9 1 5 4 3
8 7 6 1 2

Sample #2:
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2

Sample Output：

Sample #1:
1
1

Sample #2:
1
3

HINT：

Sample #1:
只需要在海拔為9 的那座城市中建造蓄水廠，即可滿足要求。

Sample #2:

上圖中，在3 個粗線框出的城市中建造蓄水廠，可以滿足要求。以這3 個蓄水廠為源頭。
在乾旱區中建造的輸水站分別用3 種顏色標出。當然，建造方法可能不唯一。

Source：

NOIP 2010 提高組

Problem Setter

hanhan0912

Testdata：

Test	Time	Memory	Score
0-1	1000ms	131072kb
0-2	1000ms	131072kb
1	1000ms	131072kb	10
2	1000ms	131072kb	10
3	1500ms	131072kb	10
4	1000ms	131072kb	10
5	1000ms	131072kb	10
6	1000ms	131072kb	10
7	1000ms	131072kb	10
8	1000ms	131072kb	10
9	1000ms	131072kb	10
10	1000ms	131072kb	10

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2808 秒，使用記憶體: 2.87MB 。