1230 . 尋寶問題

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

64.3% (18/28)

Submission's AC Ratio

16.9% (28/166)

Tags

TOI TOI-pre 2005-TOI-pre

Description

理查與威爾得到得到了一張消失多年的藏寶圖，這些寶藏埋藏在一個山洞中。傳說這個山洞曾經受到惡魔的詛咒，一次只能由一個人進入，每個人也只有一次進去的機會。而且每個人在山洞中所走過的路徑不能再走第二遍，因為身上所留下來獨特的氣味會招來惡魔的注意。

如今給定一個 m×n 藏寶圖，請你為理查與威爾設計出能拿到最多寶藏的路徑。理查將先行進入尋寶，等理查出來之後，威爾才能進入；而理查已取得之寶藏，威爾將無法取得。

※ (0,0) 在地圖的左上角。

2024/02/28 Update by FHVirus: 每個人只能走上下左右相鄰的格子，保證起終點皆可以通過，且存在一條從起點到終點的路徑。

Input Format

輸入檔第一行含有兩個正整數 m,n，表示地圖的大小有 m×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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 4000 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5
Submit out of contest
Back to Top