i793: pC. WAKUWAKU 尋找興奮源 (⌓‿⌓)
Tags : BFS
Accepted rate : 14人/14人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-09-15 04:25

Content

安妮亞是一位小學一年級學生(但實際上她只有 4 歲)
她每天最喜歡做的事,就是尋找能讓她興奮(WAKUWAKU)的來源。

 

伊甸學園坐落於一個 R 列、 C 行的矩形,
左上角座標 (0, 0),右下角座標 (R-1, C-1)

 

對於每格的狀態,我們可以用數字來表示:
0 表示該處可以通行
1 表示該處有障礙物
2 表示該處有能夠讓安妮亞興奮(WAKUWAKU)的東西

 

已知安妮亞一開始在第 a 列、第 b 行,也就是位置 (a, b)
每步只能向周圍(上、下、左、右)四個方向走一格。

 

其中能夠讓安妮亞興奮(WAKUWAKU)的東西可能不只一個。
並可以假設伊甸學園外圍四邊皆以障礙物包覆,且初始位置 (a, b) 必定不會是障礙物。

 

舉例來說,假設 R = 8, C = 7
每格狀態為:
1 1 1 1 1 1 1
1 0 1 2 1 1 1
1 0 0 1 0 2 1
1 0 0 0 0 1 1
1 0 1 1 1 1 1
1 0 1 2 1 2 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1

假設一開始位於 (1, 1) 也就是標示為綠字的地方,
則至少經過 7 步,也就是標示為紅字的路徑後,就能夠順利找到離她最近的興奮源。

 

請協助撰寫程式,計算安妮亞最少要走幾步,
才能夠找到任何會讓她興奮(WAKUWAKU)的東西?

 

WAKUWAKU 好興奮啊 (⌓‿⌓)

Input

第一行有四個正整數 R, C, a, b,
代表總列數、總行數、起點列、起點行
3 ≤ R, C ≤ 1000
0 < a < R-1
0 < b < C-1

接著有 R 列,每列有 C 行,代表學園每格狀態
狀態標示如題目敘述

Output

最少要走幾步,
才能夠找到任一會讓人興奮(WAKUWAKU)的東西

如果不論怎麼走都找不到的話,則請印出"WAKUWAKU"

Sample Input #1
8 7 1 1
1 1 1 1 1 1 1
1 0 1 2 1 1 1
1 0 0 1 0 2 1
1 0 0 0 0 1 1
1 0 1 1 1 1 1
1 0 1 2 1 2 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
Sample Output #1
7
Sample Input #2
7 5 1 1
1 1 1 1 1
1 0 1 2 1
1 0 0 1 1
1 0 0 0 1
1 0 1 0 1
1 1 2 1 1
1 1 1 1 1
Sample Output #2
WAKUWAKU
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <10M
公開 測資點#16 (5%): 2.0s , <10M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <10M
Hint :

10%:除外圍四邊外,無任何障礙物
10%:R, C ≤ 10

30%:只會有一個興奮源
50%:無特別限制 

Tags:
BFS
出處:
111學年度hgsh校內賽 [管理者: mushroom.cs9...(mushroom) ]


ID User Problem Subject Hit Post Date
32190 mushroom.cs9...(mushroom) i793
題解
29 2022-09-20 09:56