2557 問題 A: 藍橋杯2019年第十屆國賽真題-大胖子走迷宮
時間限制: 1s
內(nèi)存限制: 128MB 提交: 677 解決: 208
題目描述
小明是個大胖子,或者說是個大大胖子,如果說正常人占用 1 × 1 的面積,小明要占用 5 × 5 的面積。
由于小明太胖了,所以他行動起來很不方便。當玩一些游戲時,小明相比小伙伴就吃虧很多。小明的朋友們制定了一個計劃,幫助小明減肥。計劃的主要內(nèi)容是帶小明玩一些游戲,讓小明在游戲中運動消耗脂肪。走迷宮是計劃中的重要環(huán)節(jié)。朋友們設計了一個迷宮,迷宮可以看成是一個由 n × n 個方陣組成的方陣,正常人每次占用方陣中 1 × 1 的區(qū)域,而小明要占用 5 × 5 的區(qū)域。小明的位置定義為小明最正中的一個方格。迷宮四周都有障礙物。為了方便小明,朋友們把迷宮的起點設置在了第 3 行第 3 列,終點設置在了第 n 2 行第 n 2 列。小明在時刻 0 出發(fā),每單位時間可以向當前位置的上、下、左、右移動單位 1 的距離,也可以停留在原地不動。小明走迷宮走得很辛苦,如果他在迷宮里面待的時間很長,則由于消耗了很多脂肪,他會在時刻 k 變成一個胖子,只占用 3 × 3 的區(qū)域。如果待的時間更長,他會在時刻 2k 變成一個正常人,只占用 1 × 1 的區(qū)域。注意,當小明變瘦時迷宮的起點和終點不變。
請問,小明最少多長時間能走到迷宮的終點。注意,小明走到終點時可能變瘦了也可能沒有變瘦。
輸入
輸入的第一行包含兩個整數(shù) n, k。
接下來 n 行,每行一個由 n 個字符組成的字符串,字符為 + 表示為空地,
字符為 * 表示為阻礙物。
樣例輸入
9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++