2176 問題 F: 信息學(xué)奧賽一本通T1251-仙島求藥
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 217 解決: 97
題目描述
少年李逍遙的嬸嬸病了，王小虎介紹他去一趟仙靈島，向仙女姐姐要仙丹救嬸嬸。叛逆但孝順的李逍遙闖進(jìn)了仙靈島，克服了千險(xiǎn)萬難來到島的中心，發(fā)現(xiàn)仙藥擺在了迷陣的深處。迷陣由M×N個(gè)方格組成，有的方格內(nèi)有可以瞬秒李逍遙的怪物，而有的方格內(nèi)則是安全?，F(xiàn)在李逍遙想盡快找到仙藥，顯然他應(yīng)避開有怪物的方格，并經(jīng)過最少的方格，而且那里會(huì)有神秘人物等待著他?，F(xiàn)在要求你來幫助他實(shí)現(xiàn)這個(gè)目標(biāo)。
下圖 顯示了一個(gè)迷陣的樣例及李逍遙找到仙藥的路線。
輸入
輸入有多組測(cè)試數(shù)據(jù). 每組測(cè)試數(shù)據(jù)以兩個(gè)非零整數(shù) M 和 N 開始，兩者均不大于20。M 表示迷陣行數(shù), N 表示迷陣列數(shù)。接下來有 M 行, 每行包含N個(gè)字符,不同字符分別代表不同含義:
1)‘@’：少年李逍遙所在的位置；
2)‘.’：可以安全通行的方格；
3)‘#’：有怪物的方格；
4)‘*’：仙藥所在位置。
當(dāng)在一行中讀入的是兩個(gè)零時(shí)，表示輸入結(jié)束。
1)‘@’：少年李逍遙所在的位置；
2)‘.’：可以安全通行的方格；
3)‘#’：有怪物的方格；
4)‘*’：仙藥所在位置。
當(dāng)在一行中讀入的是兩個(gè)零時(shí)，表示輸入結(jié)束。
輸出
對(duì)于每組測(cè)試數(shù)據(jù)，分別輸出一行，該行包含李逍遙找到仙藥需要穿過的最少的方格數(shù)目(計(jì)數(shù)包括初始位置的方塊)。如果他不可能找到仙藥, 則輸出 -1。
樣例輸入
8 8 .@##...# #....#.# #.#.##.. ..#.###. #.#...#. ..###.#. ...#.*.. .#...### 6 5 .*.#. .#... ..##. ..... .#... ....@ 9 6 ? .#..#. .#.*.# .####. ..#... ..#... ..#... ..#... #.@.## .#..#. 0 0
樣例輸出
10 8 -1
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情
比賽公告
題號(hào)：2171,2172,2173,2174,2175,2176,2177,2178,2179,2180
點(diǎn)擊上方導(dǎo)航欄的訓(xùn)練，點(diǎn)擊題庫，尋找題號(hào)即可找到對(duì)應(yīng)題目，比賽結(jié)束后，請(qǐng)通過訓(xùn)練->題庫->尋找對(duì)應(yīng)題目的方式做題
因?yàn)椴淮_定因素太多，就不再安排大家輪流講題了，大家做不出題可以在測(cè)試結(jié)束后去題庫找對(duì)應(yīng)的題目看題解，希望大家自覺練習(xí)，認(rèn)真練習(xí)，考核測(cè)試會(huì)采取不同與現(xiàn)在測(cè)試的方式，兩個(gè)月后綜合測(cè)試成績不達(dá)標(biāo)者會(huì)退出實(shí)驗(yàn)室，希望大家認(rèn)真對(duì)待