1230 . 尋寶問題
TopCoder
Tags
Description
理查與威爾得到得到了一張消失多年的藏寶圖，這些寶藏埋藏在一個山洞中。傳說這個山洞曾經受到惡魔的詛咒，一次只能由一個人進入，每個人也只有一次進去的機會。而且每個人在山洞中所走過的路徑不能再走第二遍，因為身上所留下來獨特的氣味會招來惡魔的注意。
如今給定一個 $m \times n$ 藏寶圖，請你為理查與威爾設計出能拿到最多寶藏的路徑。理查將先行進入尋寶，等理查出來之後，威爾才能進入；而理查已取得之寶藏，威爾將無法取得。
※ $(0,0)$ 在地圖的左上角。
2024/02/28 Update by FHVirus: 每個人只能走上下左右相鄰的格子，保證起終點皆可以通過，且存在一條從起點到終點的路徑。
Input Format
輸入檔第一行含有兩個正整數 $m,n$，表示地圖的大小有 $m \times n$ 個方格。$m,n$ 至多為 $7$，最小為 $1$。接下來有 $m$ 行輸入，每行包含 $n$ 個字元，中間以空格隔開。若字元為 x，則表示此方格不能通過。若字元為 0~9，表示此方格所藏之寶藏數。起點在 $(0,0)$，終點在 $(m-1,n-1)$。注意！自己走過之方格不能重覆再走，除非換人。
Output Format
請由螢幕輸出理查與威爾兩人所能得到的最多寶藏總數。
Sample Input 1
2 3 7 0 6 1 2 1
Sample Output 1
17
Sample Input 2
3 5 0 x 2 8 2 2 3 x 8 2 1 1 0 1 1
Sample Output 2
29
Sample Input 3
5 6 0 1 0 0 1 0 8 x 1 x x 1 0 1 0 1 0 0 8 x x x x 1 0 0 8 0 0 0
Sample Output 3
31
Hints
Problem Source
原 TIOJ1230 / TOI2005 初選 (prob 2)。
2024/02/28 Update: Added $\LaTeX$ and details by FHVirus.
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |