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 分): 無特別限制
第一行有一個正整數 N (2<=N<=10^3) 表示 N×N 的方格 。 第 二行有兩個整
數，以一個空白隔開，代表最後一次看到狗的位置。 接下來 N 行 為城市地圖
每一行都有 N 個正整數， 整數間以一個空白隔開 ；第 i 行的數列表示 H 座標為
i-3 的橫軸,每個數列第 j 個數字的 L 座標為 j-1 。 輸入的每一個數值皆可以被
32 位元的有號整數變數儲存。
輸出一行正整數，為小明的狗可能走到的格子數目 。
範例說明3： 狗可能所在的格子有 (0,0)、(1,0)、(1,,1)、(2,,0)、(2,1)、(2, 2)，共 6 格。
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
17
4 2 1 6 4 8 3 8 8 8 3 8 5 4 4 1 3 3 9
8
3 1 1 4 9 4 4 5 9 4 3 3
6
公開 測資點#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
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 33901 |
|
f170 | 211 | 2023-02-11 23:44 | |
| 31164 |
|
f170 | 303 | 2022-07-16 18:56 | |
| 23366 | l88102412 (ouo) | f170 | 829 | 2020-11-11 00:54 |