2295 問(wèn)題 I: 藍(lán)橋杯2018年第九屆真題-迷宮與陷阱
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 1512 解決: 306
題目描述
小明在玩一款迷宮游戲，在游戲中他要控制自己的角色離開一間由NxN個(gè)格子組成的2D迷宮。
小明的起始位置在左上角，他需要到達(dá)右下角的格子才能離開迷宮。
每一步，他可以移動(dòng)到上下左右相鄰的格子中（前提是目標(biāo)格子可以經(jīng)過(guò)）。
迷宮中有些格子小明可以經(jīng)過(guò)，我們用'.'表示；
有些格子是墻壁，小明不能經(jīng)過(guò)，我們用'#'表示。
此外，有些格子上有陷阱，我們用'X'表示。除非小明處于無(wú)敵狀態(tài)，否則不能經(jīng)過(guò)。
有些格子上有無(wú)敵道具，我們用'%'表示。
當(dāng)小明第一次到達(dá)該格子時(shí)，自動(dòng)獲得無(wú)敵狀態(tài)，無(wú)敵狀態(tài)會(huì)持續(xù)K步。
之后如果再次到達(dá)該格子不會(huì)獲得無(wú)敵狀態(tài)了。
處于無(wú)敵狀態(tài)時(shí)，可以經(jīng)過(guò)有陷阱的格子，但是不會(huì)拆除/毀壞陷阱，即陷阱仍會(huì)阻止沒(méi)有無(wú)敵狀態(tài)的角色經(jīng)過(guò)。
給定迷宮，請(qǐng)你計(jì)算小明最少經(jīng)過(guò)幾步可以離開迷宮
輸入
第一行包含兩個(gè)整數(shù)N和K。 (1 <= N <= 1000 1 <= K <= 10)
以下N行包含一個(gè)NxN的矩陣。
矩陣保證左上角和右下角是'.'。
輸出
一個(gè)整數(shù)表示答案。如果小明不能離開迷宮，輸出-1。
樣例輸入
5 3
...XX
##%#.
...#.
.###.
.....
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情