Rejudge 公告 875 已更新範圍並 rejudge
IOICamp 2024 題目公開！ 連結
程式解題社網站 程式解題社網站上線了！

810 . 競速破關

Submit

Status

Discussion / Solution

Ranklist

Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Description

作為一個競速破關玩家 (speedrunner)，你對「撿金幣」遊戲地圖瞭若指掌。一開始玩家會從左上角 $(0, 0)$ 開始，並走到右下角 $(N - 1, M - 1)$ 再回到 $(0, 0)$ 算過關。每次只能移動到相鄰的格子，相鄰格子是指有共同邊。在某些格子上有障礙物，有障礙物的格子不能經過，而在沒有障礙物的格子上有些有一枚金幣，經過就可以搜集金幣。

因為你的目標還是 speedrun，你要在 $2 (N + M - 2)$ 秒過關，你想知道在此條件下，最多能搜集多少金幣。

Input Format

輸入第一行有兩個空白分的正整數 $N, M$ ，分別表示地圖的長寬。
接下來的 $N$ 行，每一行都有 $M$ 個空白分隔的整數 $a_{i j}$ ，當 $a_{i j} = 0$ 時表示該格是普通格子， $a_{i j} = 1$ 時表示該格有金幣， $a_{i j} = - 1$ 時表示該格有障礙物。

輸入保證 $1 \leq N, M \leq 100$ ， $- 1 \leq a_{i j} \leq 1$ 。

Output Format

請輸出一個整數代表最多可搜集的金幣。請注意有可能你無論如何都無法在 $2 (N + M - 2)$ 秒內通關，此時請輸出 $0$ 。

Sample Input 1

2 3
1 0 -1
1 0 1

Sample Output 1

Hints

Problem Source

北市賽

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	0~15	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2