e585. 12797 - Letters
標籤 : DFS、BFS
通過比率 : 54人/63人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-27 13:52

內容

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

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

輸入說明

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

輸出說明

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
31193 shaogan10555 ... (少干) e585
425 2022-07-18 13:36