2079 問(wèn)題 C: 找尋小妖
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 368 解決: 107
題目描述
聽(tīng)朋友說(shuō)一起來(lái)捉妖很好玩，小V也下載了這個(gè)游戲，他發(fā)現(xiàn)在虛擬地圖(M*N)上面有一個(gè)位置顯示的有一只胡巴，小V非常喜歡胡巴，想要以最快的速度捉到它，但是虛擬地圖中沒(méi)有障礙的地方
在真實(shí)的世界(M*N)中是有很多障礙的（有障礙的地方小V無(wú)法通行，小V在移動(dòng)的過(guò)程中只能上下左右移動(dòng)，無(wú)法斜著移動(dòng)），小V每移動(dòng)一格，就消耗1min，現(xiàn)在要求你來(lái)幫助他計(jì)算出所需要的最短時(shí)
間，如果無(wú)法捉到這只胡巴，輸出“Impossibility!”。
輸入
第一行輸入兩個(gè)非零整數(shù) M 和 N，兩者均不大于 100， M表示地圖的行數(shù)，N表示地圖的列數(shù)
接下來(lái)有 M 行，每行包含 N 個(gè)字符，不同字符代表不同含義：
1）、‘@’：表示小 V 所在的位置；
2）、‘.’：可以安全通過(guò)的位置
3）、‘#’：有障礙的地方
4）、‘*’：胡巴所在的位置
輸出
輸出一行，改行包含小V最短時(shí)間內(nèi)捉到胡巴的時(shí)間，如果無(wú)法捉到這只胡巴，則輸出“Impossibility!”。
樣例輸入
8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情