TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

76.9% (10/13)

Submission's AC Ratio

65.5% (19/29)

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

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

Case 1: 14
Case 2: 10

Hints

Problem Source

原TIOJ1601 / Problem Setter: ATP

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 262144
1 2000 65536 262144
2 2000 65536 262144
3 2000 65536 262144
4 2000 65536 262144