TopCoder

User's AC Ratio

70.0% (7/10)

Submission's AC Ratio

16.7% (13/78)

Description

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

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

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

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

Sample Input #1:

2 3
7 0 6
1 2 1

Sample Input #2:

3 5
0 x 2 8 2
2 3 x 8 2
1 1 0 1 1

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

Sample Output #1:

17

Sample Output #2:

29

Sample Output #3:

31

Hints

Problem Source

原TIOJ1230 / TOI2005初選(prob 2)。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 65536 262144
1 900 65536 262144
2 4000 65536 262144
3 900 65536 262144
4 900 65536 262144