很一般蛋沒有想讓你解出來的迷宮問題

發布時間: Dec. 19, 2024, 7:50 p.m.   最後更新時間: Jan. 11, 2025, 10:53 p.m.   時間限制: 200ms   記憶體限制: 128M

在一個由義大利麵佐助42號混凝土與第七代火影簽名的拉麵湯頭混合澆築而成的迷宮裡,規則其實不需要遵守,因為規則本身已經飄散在天邊,像一坨被風吹走的薯條。你從左上角的 Spaghetti 之門起跑,那裡飄著淡淡的羅勒香,氣氛凝重而微妙,像一隻穿著貝殼內搭的龍蝦,踢踏著舞鞋在神秘的數字地磚上咚咚咚地前進。

每當你跨過一格寫著 1~9 的空地時,那顆寶石就像一場哲學討論——發光、炫目、閃爍著宇宙的哀鳴。你低頭一看,它寫著:「收下我吧,你的存在將與我同輝。」於是你順手一拿,卻發現腳下的地板突然融化,變成檸檬布丁般的半流體,冒著意味不明的泡泡,味道鹹中帶甜,彷彿是你失敗料理的靈魂再現。你只能硬著頭皮,像Baby Shark一樣,左右搖晃地前行,無法回頭,因為回頭的後果是無限鱷魚口香糖,黏住你的鞋底,然後番茄醬會在牆上留下巨大的笑臉,悠悠地看著你,發出刺耳的「可愛喔...真是同情你的遭遇……」。

牆壁#,那些堅硬無比的牆壁,它們不是普通的牆壁,而是每一個你熬夜打排位時的掉星惡夢,冷冷地擋在你前方,還帶著一股在深夜想吃泡麵卻發現泡麵只剩湯的失落感。你嘗試撞開它們,牆壁會發出悶哼一聲,然後變成Box Light,突然出現的吾黃萬萬歲,朗讀莎士比亞的十四行詩:「你來晚了,迷路者。真理不在你手上,只有寶石與未完成的明天。」

突然,E fghijk 出現了——一個字母表外的神祕存在,發著霓虹燈的光芒,像從廣廣沙漠中騰空而起的百事可樂,終於與氣泡重逢。音樂在這一刻響起,聽起來像是 Spike Down 的低語,卻混雜著挖掘機施工現場的噪音,讓你懷疑是不是世界在嘲笑你。你想起自己曾經用「watch your eyes」隨手丟出的技能,畫面亮到讓瞳孔懷疑人生,只能用肌肉記憶像犀牛一樣,帶著「路是人撞出來的」的氣勢,一頭扎進未知的前方。

沿途寶石閃閃發亮,像是給你在宇宙深處開的小燈,讓你忘記現實的痛苦,只記得這是一場意識與麵條、混凝土、寶石交織的電音派對。最終,迷宮會緩慢變形,像是失去角色的 NPC 試圖加入你的隊伍,嘴裡碎碎念著:「是不是忘了開權限,給我一個出場機會!」

收集所有寶石,證明你額頭上的血輪眼可以看穿一切謎題、守護 Spaghetti 的榮耀。如果你聽見遠方傳來義大利麵條般纏繞的嘆息聲,那只是迷宮在祝福你:「下一場,你可能還是會迷路,但至少這一次,你很帥。」

恭喜你浪費這麼多時間看沒用的東西,上面都說了規則不是這樣的…(~_<)

給定一個NxM的迷宮,迷宮的每個格子可能是以下幾種類型之一:
.:可通行的空地。
#:不可通行的牆壁。(我直接告訴你牆壁的生成機率為0.4)
S:起始點(迷宮中唯一一個)。 (確保起點位於左上角)
E:終點(迷宮中唯一一個)。 (確保終點一定在最底下一行)
數字 1∼9:包含寶石的格子,數字表示該格子的寶石價值。
你需要從起點 S 出發,走到終點 E,並收集路徑上所有的寶石。你只能上下左右移動,且每個格子只能進入一次。請計算能夠收集的最大寶石價值。


(本題有隱藏題 !! 想破台請加油 !!)

第一行輸入兩個正整數 N,M (1<NxM<=10^2)(分別表示迷宮的行數和列數)。
接下來的N行,每行包含一個長度為M的字串,表示迷宮的地圖。

輸出一個整數,表示從起點 S 到終點 E 能收集的最大寶石價值。如果無法到達終點,輸出-1。

複製範例
8 7
S.##1#.
.6#255#
.#57#17
9.26#7.
.#2.3##
616#.##
9.###26
E##.###
59

BFS ???    DFS ?????   DP ?????????

番茄醬佐助卡卡西


在首頁尋找框內輸入  "2bBdAeQ0I2sNoUhc"  說不定有意外驚喜

dfs

竹中軟研40th第一次競賽(社內賽)