TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

75.8% (25/33)

Submission's AC Ratio

54.7% (52/95)

Tags

Description

你有一面破碎的鏡子。

但很不幸地你現在並不是在打魔城馬車(Die Kutschfahrt zur Teufelsburg),這面鏡子跟別人交易時一直被別人拒絕。
又因為鏡面有些破損,你也不能拿來照。

有一天你發現你可以一次將任意兩條直行交換,也可以一次將任意兩條橫行交換。

例如對於以下的鏡子 (以0表示鏡子的破裂處、1表示鏡子完好處)

1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 1 1 1 1

你可以將左邊數來第二、三直行交換變成:
1 1 1 1 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

然後再將上面數下來第一、二橫行交換:

1 0 1 0 1
1 1 1 1 1
1 1 0 0 1
1 1 1 1 1

形成以上鏡子。當然,這面鏡子是你的,你想做幾次交換都隨便你,也沒有那麼無聊說你交換要花費多少金錢或是只能換最少次。

「我只是想要一面能交易的鏡子。」你的想法就這麼簡單。

能交易的鏡子需要形狀為一矩形,並且裡面所有的數字都是1。

而貪心(Greedy)的你,則希望能交易的鏡子周長越大越好。

※每面輸入的鏡子最外面一整圈皆無破損,即皆為1

Input Format

輸入含多筆測資。

每筆測資第一行包含兩個數字n, m ( 0 < n, m <= 200)

接下來包含n行,每行包含m個數字描述這面鏡子。

Output Format

對每一筆輸入資料,輸出一行描述這是第幾個Case,並輸出最大能交易的鏡子的周長大小。

(Case由1開始編號,注意Case和數字、冒號和輸出數字之間皆有一個空白。)

Sample Input 1

4 5
1 1 1 1 1
1 0 0 1 1
1 1 0 0 1
1 1 1 1 1
3 3
1 1 1
1 0 1
1 1 1

Sample Output 1

Case 1: 14
Case 2: 10

Hints

Problem Source

原TIOJ1601 / Problem Setter: ATP

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5