TopCoder

User's AC Ratio

86.9% (53/61)

Submission's AC Ratio

26.2% (84/321)

Description

馬利與路易是一對熱愛尋寶的兄弟,這天他們拿到一張藏寶地圖,地圖上記載著一個地底迷宮的通道與寶藏位置。地圖的樣式如下:

迷宮的入口固定在左上角,出口固定在右下角;星星記號代表寶藏,塗黑的方格代表牆壁,無法進入。每一分鐘馬路兄弟可以移動一格(如果可以進入的話),例如可以從位置 $(2, 4)$ 移到 $(3, 4)$ 或 $(2, 3)$。由於迷宮裡充滿毒氣,他們必須儘快離開;若迷宮的大小為 $M\times N$,他們只能在裡面待 $(M+N-2)$ 分鐘,也就是可以由入口移動 $(M+N-2)$ 格抵達出口。

馬路兄弟可以一起行動,也可以分開。以上圖為例,他們一開始可以一起走到 $(2, 4)$ 的位置,然後馬利走向 $(2, 3)$,路易走向 $(3, 4)$,最後搜集到 $5$ 個寶藏。注意:位在 $(2, 4)$ 的寶藏只能算一份,而位在 $(5, 4)$ 的寶藏無法取得(因為會來不及離開迷宮)。

請你撰寫一個程式,給定迷宮地圖,求出他們最多可以搜集到幾個寶藏?可以假設入口和出口一定不會是牆壁,但有可能有寶藏。有些迷宮很危險,可能進去就出不來,或者雖可安全離開但會空手而回。

Input Format

第一列有兩個正整數 $M$ 和 $N$ $(2\leq M, N\leq 100)$,代表地圖有幾列與幾行。接下去有 $M$ 列,每一列有 $N$ 個整數值,$1$ 代表寶藏,$0$ 代表空地(可進入),$-1$代表牆壁(不可進入)。輸入中,兩個整數間以至少一個空白隔開。

Output Format

輸出馬路兄弟最多可以搜集到幾個寶藏。

Sample Input

輸入範例 1(題目敘述)
4 5
0 1 1 0 1
-1 0 0 -1 -1
0 0 1 1 0
0 1 0 0 0

輸入範例 2
3 3
0 -1 0
-1 0 0
0 0 0

輸入範例 3
4 5
1 0 1 0 0
1 0 0 0 0
0 0 1 1 0
1 1 0 0 1

Sample Output

輸出範例 1
5

輸出範例 2
0

輸出範例 3
8

Hints

本題共有三組測試資料,每組可有多筆測試資料:
第一組測試資料 $2 \leq M, N \leq 6$,共 25 分;
第二組測試資料 $10 \leq M, N \leq 100$,地圖中已知不超過兩個寶藏,共 16 分;
第三組測試資料 $10 \leq M, N \leq 100$,共 59 分。

Problem Source

108 北市賽 pE
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~7 $2 \leq M, N \leq 6$ 25
2 8~14 $10 \leq M, N \leq 100$,地圖中已知不超過兩個寶藏 16
3 0~29 $10 \leq M, N \leq 100$ 59

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 262144 65536 1 3
1 500 262144 65536 1 3
2 500 262144 65536 1 3
3 500 262144 65536 1 3
4 500 262144 65536 1 3
5 500 262144 65536 1 3
6 500 262144 65536 1 3
7 500 262144 65536 1 3
8 500 262144 65536 2 3
9 500 262144 65536 2 3
10 500 262144 65536 2 3
11 500 262144 65536 2 3
12 500 262144 65536 2 3
13 500 262144 65536 2 3
14 500 262144 65536 2 3
15 500 262144 65536 3
16 500 262144 65536 3
17 500 262144 65536 3
18 500 262144 65536 3
19 500 262144 65536 3
20 500 262144 65536 3
21 500 262144 65536 3
22 500 262144 65536 3
23 500 262144 65536 3
24 500 262144 65536 3
25 500 262144 65536 3
26 500 262144 65536 3
27 500 262144 65536 3
28 500 262144 65536 3
29 500 262144 65536 3