Problem : 394 - 壞掉的水表

Problem Statistics

Solved Member: 25　　Submission: 73　　User Tried: 25

Statement:

Andrew 是一個很厲害的水電工人，在鎮上小有名氣，常常被呼喚來呼喚去，辛苦的修修修...修水電。

有一天，某間工廠的水表壞了，找上了 Andrew，讓他非常困擾。由於這間工廠的水表是由韜韜設計的，Andrew 沒辦法自己處理，於是他想求助於你。

這間工廠總共有 N x M 個隔間，整間工廠可以畫成一個 N x M 的方陣。
每個隔間和他的前後左右（在方陣圖中可以看成上下左右）四個隔間相鄰，最外圈的隔間為邊界，所以不與更外一圈相鄰。
兩個相鄰隔間之間可能會有一條流量為 K 的水管管線（每條管線的流量 K 可能不一樣），水表記錄的就是隔間之間的流量。
但是當初韜韜在設計水表時，他覺得記錄四個方向的流量太浪費成本了，於是他把四個方向的流量加總起來，並記錄在水表上。

附圖是範例測資一的示意圖，由於沒有流量通往中間的方塊，所以中間方塊的總和應該是 0。

今天在這 N x M 個隔間中，記錄某一個隔間流量的水表壞了，使得 Andrew 沒有辦法知道該隔間原本的流量，請問你能幫他查出應該是多少嗎？

為了簡化輸入，壞掉的隔間流量用 -1 表示。

Input:Output:

輸入的第一行有兩個正整數 N、M，分別代表工廠水表方陣圖的長寬。
接下來會有 N 行，每一行有 M 個數字，代表方陣圖的詳細情況，其中壞掉的那一格用 -1 表示，我們保證輸入中的 -1 恰有一個。

1 ≤ N, M ≤ 1000
0 ≤ K ≤ 100 （K為四方向流量總和，所以一格最大值是400）

在佔分 50% 的測試資料中，我們保證 1 ≤ N, M ≤ 50, 0 ≤ K ≤ 1，因此一格中最大的值是 4 。

請輸出一個數字，代表水表壞掉的那一格流量應該是多少。
請注意，該隔間可能會根本沒有流入或流出，此時流量會是 0 。
如果你覺得答案可能不只一種，請把題目再看過一遍。

Sample Input:Sample Output:

3 3
1 1 2
1 -1 2
1 1 1

Source:

104資奧校內初選

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1	1000ms	262144kb	10
2	1000ms	262144kb	10
3	1000ms	262144kb	10
4	1000ms	262144kb	10
5	1000ms	262144kb	10
6	1000ms	262144kb	10
7	1000ms	262144kb	10
8	1000ms	262144kb	10
9	1000ms	262144kb	10
10	1000ms	262144kb	10