f170. m5a1-尋找小狗(Dog)
Tags : BFS Flood fill
Accepted rate : 223人/275人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-08-05 00:28

Content

TOI練習賽 2020m5a1-尋找小狗(Dog)  原題連結

問題敘述
小明的狗在一座城市裡走失了。這座城市很特別,它的土地可以分為N×N
個正方形小格,每一格都有自己的海拔高度 。 縱軸座標為 H ,橫軸座標為 L 。如
下圖所示 ,最外層為座標 。

一個格子與其 上、下、左、右的格子相通,但是不能超出城市範圍 。例如可以從
格子(2,2)走到(2,1)、(1,2)、(2,3)、和(3,2)。如果在邊緣處 像是 (1, 0),不
能超出城市範圍,因此只能往(0,0)、(1,1)和 (2,0) 移動 。
小明的狗很懶惰, 如果兩個相鄰的格子海拔高度差距超過 2 單位,牠就不
會走過去。例如狗在(2,2),雖然與(1,2)相鄰,但由於海拔差距為 3 因 此牠
不會直接走到(1,2)。 不過牠仍有可能走到(1,2),例如牠可依序經由(2,3)和
(1,3) 到達 (1,2) 。
小明想要地毯式搜尋他的狗,找遍牠所有可能走到的格子 。 請寫一個程式,
計算出小明的狗可能走到的格子數目 。

 

評分說明
此題目測資分成三 組,每組測資有多筆測試資料,需答對該組所有測試資料
才能獲得該組分數,各組詳細限制如下。
第一組(10 分): N= 2
第二組(30 分): 2<= N<=20
第三組(60 分): 無特別限制

Input

第一行有一個正整數 N (2<=N<=10^3) 表示 N×N 的方格 。 第 二行有兩個整
數,以一個空白隔開,代表最後一次看到狗的位置。 接下來 N 行 為城市地圖
每一行都有 N 個正整數, 整數間以一個空白隔開 ;第 i 行的數列表示 H 座標為
i-3 的橫軸,每個數列第 j 個數字的 L 座標為 j-1 。 輸入的每一個數值皆可以被
32 位元的有號整數變數儲存。

 

Output

輸出一行正整數,為小明的狗可能走到的格子數目 。

範例說明3: 狗可能所在的格子有 (0,0)、(1,0)、(1,,1)、(2,,0)、(2,1)、(2, 2),共 6 格。

 

Sample Input #1
5
2 2
2 3 4 7 8
1 5 2 3 7
6 5 3 4 8
2 4 6 7 1
1 6 3 4 3
Sample Output #1
17
Sample Input #2
4
2 1 
6 4 8 3
8 8 8 3
8 5 4 4
1 3 3 9
Sample Output #2
8
Sample Input #3
3
1 1
4 9 4
4 5 9
4 3 3
Sample Output #3
6
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint :
Tags:
BFS Flood fill
出處:
TOI練習賽2020年5月潛力組 [管理者: p3a_owhj (阿普二信) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
33901 elephant6107 ... (yee elephant) f170
DFS會TLE,用BFS
292 2023-02-11 23:44
31164 cubeman94033 ... (請輸入暱稱) f170
不要遞迴
398 2022-07-16 18:56
23366 l88102412 (ouo) f170
關於超時
909 2020-11-11 00:54