星际战争I(Normal)

星际战争I(Normal)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

现在是星际战争的第一个年头。
绝地武士躲藏在一颗大小为\(N \times M\) 的矩形二维星球上。
贸易联盟想要消灭他们,但是经历过之前的战斗之后,贸易联盟知道:
铁罐头是打不过绝地武士的!
所以他们决定展开轰炸。
受限于技术,贸易联盟的轰炸机无法轰炸星球的边缘(最靠外的格子)。
丢下一枚炸弹会对目标格造成4点破坏,对具有邻边的4个格子造成1点伤害。
可以重复轰炸同一个格子,所有格子的伤害值累加

0 0 0 0 0
0 0 1 0 0
0 1 4 1 0
0 0 1 0 0
0 0 0 0 0

经过不知道多少次轰炸后,贸易联盟获得了对这个星球破坏状况的信息,除了一个格子之外。
你的上级交给了你一个任务,要你给你自己的脑袋写个程序,来计算对这个格子的伤害。
由于硬件的限制,你的芯片只剩下10个int的空间,如果超过,你的脑袋就会booooooom。

Format

Input

输入第一行为两个正整数N,M (0< N,M <=1000),表示星球的行数、列数
接下来N行M列的矩阵,\(a_{i,j}\)表示星球土地(i,j)上的伤害值,-1表示未知位置
(左上角为(1,1),右下角为(n,m))
数据保证除了位置位置外,其余数字的值满足\( 0 <= a_{i,j} <= 100\)
数据保证合法解存在

Output

输出仅一行一个数字,表示未知位置的伤害值。

Sample 1

Input

5 5
0 0 0 0 0
0 0 1 0 0
0 1 -1 1 0
0 0 1 0 0
0 0 0 0 0

Output

4

Sample 2

Input

26 32
0 9 4 12 10 7 7 12 10 13 13 10 9 14 13 10 4 14 10 12 15 9 9 10 3 13 16 10 5 6 9 0 
9 49 49 74 69 60 55 74 76 84 83 71 72 87 87 64 53 82 76 85 94 69 59 57 45 85 96 73 49 46 51 9 
9 63 85 94 85 91 71 79 85 82 71 78 81 81 82 75 81 91 85 94 104 71 51 56 72 99 85 86 81 67 60 9 
6 52 90 86 62 62 63 91 97 93 77 80 65 66 78 87 60 60 82 92 109 84 87 90 89 84 64 55 53 52 58 7 
7 58 78 62 41 46 58 85 74 75 77 82 75 78 80 95 50 60 86 78 90 91 111 110 104 82 72 65 68 59 77 14 
12 67 69 80 78 58 69 77 75 89 85 98 101 85 79 107 77 85 98 71 66 96 112 75 66 65 67 60 58 56 70 9 
7 61 82 84 85 68 93 84 81 77 81 82 91 82 80 103 93 89 80 76 79 96 84 62 63 62 80 90 59 63 81 13 
8 61 78 91 77 62 99 73 98 99 97 73 100 99 80 66 64 90 100 105 81 81 73 88 85 84 99 104 74 79 86 13 
13 79 80 91 61 55 86 89 101 104 95 69 87 92 89 90 103 105 109 122 89 103 67 60 82 105 94 73 84 107 85 12 
10 72 78 82 82 98 74 87 75 87 93 78 71 67 66 84 98 80 79 113 83 82 61 54 74 100 110 87 92 107 75 9 
11 83 111 98 95 111 59 62 59 78 88 97 90 69 67 72 76 71 55 80 81 90 108 88 89 80 99 79 88 94 80 12 
11 70 76 79 92 101 79 87 85 88 76 104 110 80 71 67 73 70 63 63 67 76 89 66 88 86 117 74 80 78 69 11 
8 64 81 76 97 105 106 114 94 75 62 77 72 51 61 62 80 81 69 55 82 97 92 80 105 97 102 71 86 84 49 5 
11 83 106 85 102 88 101 127 110 66 52 74 79 82 92 74 -1 73 85 61 74 84 88 77 83 86 85 62 84 85 48 6 
15 97 111 92 74 87 82 81 91 73 54 66 77 115 103 64 64 77 109 87 92 80 83 73 78 86 81 69 100 79 48 7 
12 86 95 87 63 87 73 60 67 68 48 48 56 88 65 65 100 106 100 95 91 72 83 77 89 112 103 88 108 76 45 5 
12 83 83 61 60 86 88 75 68 76 93 69 49 94 94 96 87 78 88 86 65 64 74 70 83 109 79 77 108 93 61 9 
11 76 68 57 49 61 87 81 61 75 107 77 45 81 75 77 85 92 97 88 64 55 75 77 72 55 33 58 77 77 64 8 
13 82 71 68 62 74 96 78 64 93 96 77 69 92 59 69 102 85 70 86 75 59 79 75 71 55 38 82 112 95 77 13 
10 70 72 83 87 89 83 64 61 71 75 75 62 63 56 77 74 72 50 78 98 78 73 81 63 79 67 96 108 80 56 6 
10 73 85 76 79 93 85 65 62 76 97 91 85 81 91 102 85 94 63 64 89 77 93 103 78 90 71 96 103 82 61 9 
10 67 77 76 67 68 75 62 61 102 109 78 85 102 105 100 99 71 58 47 70 57 81 92 98 103 80 72 72 69 61 9 
9 67 89 83 67 79 104 78 63 74 65 63 81 97 98 96 107 87 89 82 77 60 75 82 77 71 62 62 76 85 56 8 
9 71 95 88 73 59 87 58 52 48 68 78 68 74 80 89 106 109 80 93 79 69 71 63 65 70 53 53 60 84 49 4 
13 72 79 66 60 59 88 61 59 53 64 70 68 67 49 48 48 67 47 51 51 70 78 66 62 80 79 65 69 88 65 12 
0 13 11 9 8 8 15 8 9 8 9 10 10 11 5 7 4 10 6 6 6 11 12 10 8 12 14 8 11 13 12 0 

Output

77

Limitation

时间限制:1s
空间限制:800KiB

Hint

内存限制极小,只允许开设少量int,无法存储整个地图格子
此题需要巧解~

Source

Vijos Original

XMU ACM 摸底测试(个人赛)

未参加
状态
已结束
规则
ACM/ICPC
题目
5
开始于
2018-03-04 08:30
结束于
2018-03-04 11:30
持续时间
3.0 小时
主持人
参赛人数
55