你有一面破碎的鏡子。
但很不幸地你現在並不是在打魔城馬車(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
輸入含多筆測資。
每筆測資第一行包含兩個數字n, m ( 0 < n, m <= 200)
接下來包含n行,每行包含m個數字描述這面鏡子。
對每一筆輸入資料,輸出一行描述這是第幾個Case,並輸出最大能交易的鏡子的周長大小。
(Case由1開始編號,注意Case和數字、冒號和輸出數字之間皆有一個空白。)
原TIOJ1601 / Problem Setter: ATP
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 20 |
2 | 1 | 20 |
3 | 2 | 20 |
4 | 3 | 20 |
5 | 4 | 20 |