題目 2176:
信息學(xué)奧賽一本通T1251-仙島求藥
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 215 解決: 96
題目描述
少年李逍遙的嬸嬸病了，王小虎介紹他去一趟仙靈島，向仙女姐姐要仙丹救嬸嬸。叛逆但孝順的李逍遙闖進(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è)迷陣的樣例及李逍遙找到仙藥的路線。
輸入格式
輸入有多組測試數(shù)據(jù). 每組測試數(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é)束。
輸出格式
對于每組測試數(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)擊這里了解課程詳情