1233 . 恪鑭碼星

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

不知道該叫甚麼好
我就廢

User's AC Ratio

96.7% (88/91)

Submission's AC Ratio

32.9% (118/359)

Tags

TOI TOI-pre 2006-TOI-pre

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 1

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

Sample Output 1

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

No. Testdata Range Score
1 0 2
2 1 2
3 2 2
4 3 2
5 4 2
6 5 2
7 6 2
8 7 2
9 8 2
10 9 2
11 10 2
12 11 2
13 12 2
14 13 2
15 14 2
16 15 2
17 16 2
18 17 2
19 18 2
20 19 2
21 20 2
22 21 2
23 22 2
24 23 2
25 24 2
26 25 2
27 26 2
28 27 2
29 28 2
30 29 2
31 30 2
32 31 2
33 32 2
34 33 2
35 34 32

Testdata and Limits

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