問題敘述
小明的狗在一座城市裡走失了。這座城市很特別,它的土地可以分為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
ID | User | Problem | Subject | Hit | Post Date |
33901 | elephant6107 ... (yee elephant) | f170 | 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 |