TopCoder

User's AC Ratio

97.6% (40/41)

Submission's AC Ratio

33.8% (53/157)

Description

在星際1200年時,恪鑭碼星的科學家們研發出了一個極機密武器 – 煞剋鬾(Shocker)。煞剋鬾能使得他們的星際戰隊能在被其他星際航艦圍攻時能順利脫困。煞剋鬾啟動時,能暫時癱瘓一定範圍內其他航艦之活動力,進而使得自己得以脫困。煞剋鬾的威力有10個等級 (1, 2, …, 10),等級越高,所影響的範圍就越大。但是每次啟用煞剋鬾脫困時,就會消耗掉一定程度的啟動能源。因此每次使用時,就必須先精算所需等級,以避免浪費珍貴的啟動能源。恪鑭碼星的各航艦都配備有精密的雷達裝置,因此從雷達螢幕上能清楚的看到正在圍攻該航艦的所有敵方航艦。請你寫一個程式來快速的數出敵方艦隊的航艦數,並設定煞剋鬾啟用等級,使得該航艦能以最少的啟動能源脫困。

1.雷達顯現的影像最大為512x512。雷達影像中,每一艘敵方航艦都是以相鄰的「1」所標記。航艦跟航艦之間並不會相連(相鄰)。
2.煞剋鬾能暫時癱瘓的航艦數如下表所示:

等級12345678910
最多癱瘓航艦數1246101214161820

Input Format

輸入檔第一行有兩個以一個空白隔開的整數M, N,代表雷達螢幕大小 (M x N)。之後的M行,每一行有N個連續的0或1。

Output Format

請輸出如要脫困,煞剋鬾啟動時應設定的等級。如果雷達螢幕上沒有敵艦,則輸出 0,如有超過20艘敵艦,則輸出最大等級數。

Sample Input

10 10
0000000000
0011100010
0011000101
1010000111
1000010000
1001010000
1001100000
0001111100
0000000000
0000000000

Sample Output

3

Hints

說明:共有4艘敵艦,分別為

111 1 1 1
11 101 1 101
1 111 1 110
1 11111

註:0並不是航艦的一部份,這裡的0只是用來凸顯航艦的結構性。

Problem Source

原TIOJ1233 / TOI2006初選(prob 1)。

Subtasks

For Testdata: 0 ~ 0, Score: 2
For Testdata: 1 ~ 1, Score: 2
For Testdata: 2 ~ 2, Score: 2
For Testdata: 3 ~ 3, Score: 2
For Testdata: 4 ~ 4, Score: 2
For Testdata: 5 ~ 5, Score: 2
For Testdata: 6 ~ 6, Score: 2
For Testdata: 7 ~ 7, Score: 2
For Testdata: 8 ~ 8, Score: 2
For Testdata: 9 ~ 9, Score: 2
For Testdata: 10 ~ 10, Score: 2
For Testdata: 11 ~ 11, Score: 2
For Testdata: 12 ~ 12, Score: 2
For Testdata: 13 ~ 13, Score: 2
For Testdata: 14 ~ 14, Score: 2
For Testdata: 15 ~ 15, Score: 2
For Testdata: 16 ~ 16, Score: 2
For Testdata: 17 ~ 17, Score: 2
For Testdata: 18 ~ 18, Score: 2
For Testdata: 19 ~ 19, Score: 2
For Testdata: 20 ~ 20, Score: 2
For Testdata: 21 ~ 21, Score: 2
For Testdata: 22 ~ 22, Score: 2
For Testdata: 23 ~ 23, Score: 2
For Testdata: 24 ~ 24, Score: 2
For Testdata: 25 ~ 25, Score: 2
For Testdata: 26 ~ 26, Score: 2
For Testdata: 27 ~ 27, Score: 2
For Testdata: 28 ~ 28, Score: 2
For Testdata: 29 ~ 29, Score: 2
For Testdata: 30 ~ 30, Score: 2
For Testdata: 31 ~ 31, Score: 2
For Testdata: 32 ~ 32, Score: 2
For Testdata: 33 ~ 33, Score: 2
For Testdata: 34 ~ 34, Score: 32
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 262144
1 5000 65536 262144
2 5000 65536 262144
3 5000 65536 262144
4 5000 65536 262144
5 5000 65536 262144
6 5000 65536 262144
7 5000 65536 262144
8 5000 65536 262144
9 5000 65536 262144
10 5000 65536 262144
11 5000 65536 262144
12 5000 65536 262144
13 5000 65536 262144
14 5000 65536 262144
15 5000 65536 262144
16 5000 65536 262144
17 5000 65536 262144
18 5000 65536 262144
19 5000 65536 262144
20 5000 65536 262144
21 5000 65536 262144
22 5000 65536 262144
23 5000 65536 262144
24 5000 65536 262144
25 5000 65536 262144
26 5000 65536 262144
27 5000 65536 262144
28 5000 65536 262144
29 5000 65536 262144
30 5000 65536 262144
31 5000 65536 262144
32 5000 65536 262144
33 5000 65536 262144
34 5000 65536 262144