TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

90.5% (19/21)

Submission's AC Ratio

54.1% (33/61)

Tags

Description

在競賽圈有個潛規則,你如果想要變強,你就要去吃碗拉麵,而且你吃的拉麵越好吃,你就會變得越強。
在天龍國裡,有許多家麵店,而你手上有一張 (n×m) 的拉麵店地圖。
其中第 i 行第 j 列的個子就是 wi,j
wi,j>0 時,代表在 (i,j) 上有一間美味程度為 wi,j 的拉麵店。
wi,j=0 時,代表在 (i,j) 上面有一位競賽選手
wi,j<0 時,代表在 (i,j) 上面什麼都沒有

而且對於兩兩不同的麵店,他們的美味程度不會重複。

有許多競賽選手想要去吃拉麵。
每個人都想吃最好吃的拉麵,
可是如果大家都擠在同一間拉麵店的話,就要等很久。

聰明的你想到了一個辦法。
分別 規定所有人都只能前往和它距離 K 以內的拉麵店。
也就是說,你不需要給所有人相同的限制,如果你喜歡蕭800 那你就給他限制 K 大一點,如果你覺得蛋餅該少吃拉麵,你就限制他 K 小一點。

其中兩個座標 (x1,y1),(x2,y2) 的距離定為 max(|x1x2|,|y1y2|)

在這樣的狀況下,所有人都會前往他可以去的拉麵店中,做出最美味拉麵的店。

如此一來,就不會所有人都擠在同一間拉麵店裡了

現在,你想知道如果你好好限制大家,最多能有幾間拉麵店有人光顧

Input Format

第一行有兩個正整數 n,m(n×m300)
接下來 n 行,每行有 m個整數
其中第 i 行第 j 個代表 wij,(1wijn×m)

Output Format

輸出一個整數代表答案

Sample Input 1

3 5
-1  0  3 -1 -1
-1  2 -1  0 -1
 0  1 -1 -1  4

Sample Output 1

3

Hints

對於範測一,假如我們讓限制為 (1, 2) : 2, (2, 4) : 2, (3, 1) : 1 的話
在 (1, 2) 上的選手會到 (1, 3) 的拉麵店
在 (2, 4) 上的選手會到 (3, 5) 的拉麵店
在 (3, 1) 上的選手會到 (2, 2) 的拉麵店

Problem Source

by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0~19 nm10 10
2 0~49 n=1 30
3 0~99 no additional limits 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3
1 1000 65536 65536 1 2 3
2 1000 65536 65536 1 2 3
3 1000 65536 65536 1 2 3
4 1000 65536 65536 1 2 3
5 1000 65536 65536 1 2 3
6 1000 65536 65536 1 2 3
7 1000 65536 65536 1 2 3
8 1000 65536 65536 1 2 3
9 1000 65536 65536 1 2 3
10 1000 65536 65536 1 2 3
11 1000 65536 65536 1 2 3
12 1000 65536 65536 1 2 3
13 1000 65536 65536 1 2 3
14 1000 65536 65536 1 2 3
15 1000 65536 65536 1 2 3
16 1000 65536 65536 1 2 3
17 1000 65536 65536 1 2 3
18 1000 65536 65536 1 2 3
19 1000 65536 65536 1 2 3
20 1000 65536 65536 2 3
21 1000 65536 65536 2 3
22 1000 65536 65536 2 3
23 1000 65536 65536 2 3
24 1000 65536 65536 2 3
25 1000 65536 65536 2 3
26 1000 65536 65536 2 3
27 1000 65536 65536 2 3
28 1000 65536 65536 2 3
29 1000 65536 65536 2 3
30 1000 65536 65536 2 3
31 1000 65536 65536 2 3
32 1000 65536 65536 2 3
33 1000 65536 65536 2 3
34 1000 65536 65536 2 3
35 1000 65536 65536 2 3
36 1000 65536 65536 2 3
37 1000 65536 65536 2 3
38 1000 65536 65536 2 3
39 1000 65536 65536 2 3
40 1000 65536 65536 2 3
41 1000 65536 65536 2 3
42 1000 65536 65536 2 3
43 1000 65536 65536 2 3
44 1000 65536 65536 2 3
45 1000 65536 65536 2 3
46 1000 65536 65536 2 3
47 1000 65536 65536 2 3
48 1000 65536 65536 2 3
49 1000 65536 65536 2 3
50 1000 65536 65536 3
51 1000 65536 65536 3
52 1000 65536 65536 3
53 1000 65536 65536 3
54 1000 65536 65536 3
55 1000 65536 65536 3
56 1000 65536 65536 3
57 1000 65536 65536 3
58 1000 65536 65536 3
59 1000 65536 65536 3
60 1000 65536 65536 3
61 1000 65536 65536 3
62 1000 65536 65536 3
63 1000 65536 65536 3
64 1000 65536 65536 3
65 1000 65536 65536 3
66 1000 65536 65536 3
67 1000 65536 65536 3
68 1000 65536 65536 3
69 1000 65536 65536 3
70 1000 65536 65536 3
71 1000 65536 65536 3
72 1000 65536 65536 3
73 1000 65536 65536 3
74 1000 65536 65536 3
75 1000 65536 65536 3
76 1000 65536 65536 3
77 1000 65536 65536 3
78 1000 65536 65536 3
79 1000 65536 65536 3
80 1000 65536 65536 3
81 1000 65536 65536 3
82 1000 65536 65536 3
83 1000 65536 65536 3
84 1000 65536 65536 3
85 1000 65536 65536 3
86 1000 65536 65536 3
87 1000 65536 65536 3
88 1000 65536 65536 3
89 1000 65536 65536 3
90 1000 65536 65536 3
91 1000 65536 65536 3
92 1000 65536 65536 3
93 1000 65536 65536 3
94 1000 65536 65536 3
95 1000 65536 65536 3
96 1000 65536 65536 3
97 1000 65536 65536 3
98 1000 65536 65536 3
99 1000 65536 65536 3