e585: 12797 - Letters
Tags : DFS、BFS
Accepted rate : 20人/24人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-30 16:26

Content

邏輯城市中的公園始終是N×N正方形(2 ≤ N ≤ 100)。
其中每個正方形只具有前10個大寫英文字母(ABCDEFGHIJ)或者前10個小寫英文字母(abcdefghij)。
邏輯之城的人們在穿越公園時僅遵循一致的道路。
例如,如果他們走過小寫字母c,那麼他們以後將不允許自己走過大寫字母C。
我們稱此路徑為一致路徑,此路徑相同字母只可能以相同形式出現(僅大寫或者僅小寫)。

您必須寫一個程式來幫助邏輯之城的人們,計算出從左上角座標(1, 1)到右下角座標(N, N)的最短一致路徑。
對於以下的公園,最短一致路徑的長度為13。

公園地圖:

DdaAaA
CBAcca
eEaeeE
bBbabB
DbDdDc
ffaAaC

最短一致路徑:

D.....
C.....
e.....
b.bab.
DbD.D.
....aC
Input

輸入多組測資。
每組測資第一行有一個整數N (2 ≤ N ≤ 100),N即正方形公園的邊長。
接下來N行每行N個字元,代表公園地圖。

Output

對於每組測資,輸出此公園最短一致路徑。
如果沒有一致路徑,輸出"-1"。

Sample Input #1
6
DdaAaA
CBAcca
eEaeeE
bBbabB
DbDdDc
fFaAaC
7
aAaaaaa
aAaaaAa
aAaaaAA
aaAaAaa
AaAaaAa
aaAAaAa
aaaaaAa
Sample Output #1
13
-1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
DFS、BFS
出處:
UVA [管理者:
ig99lp33lp33 (위즈원)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」