CF22B.Bargaining Table

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Bob wants to put a new bargaining table in his office. To do so he measured the office room thoroughly and drew its plan: Bob's office room is a rectangular room n × m meters. Each square meter of the room is either occupied by some furniture, or free. A bargaining table is rectangular, and should be placed so, that its sides are parallel to the office walls. Bob doesn't want to change or rearrange anything, that's why all the squares that will be occupied by the table should be initially free. Bob wants the new table to sit as many people as possible, thus its perimeter should be maximal. Help Bob find out the maximum possible perimeter of a bargaining table for his office.

鲍勃想在他的办公室里放置一张新的谈判桌。为此,他仔细测量了办公室,并绘制了平面图:鲍勃的办公室是一个 n×mn \times m 米的矩形房间。房间中每一平方米要么被某件家具占据,要么是空闲的。谈判桌也是矩形的,且必须以边与办公室墙壁平行的方式放置。鲍勃不想移动或重新布置任何物品,因此谈判桌所占据的所有方格初始时都必须是空闲的。鲍勃希望新桌子能容纳尽可能多的人,因此其周长应尽可能大。请帮助鲍勃找出其办公室中谈判桌可能达到的最大周长。

输入格式

The first line contains 2 space-separated numbers n and m (1 ≤ n, m ≤ 25) — the office room dimensions. Then there follow n lines with m characters 0 or 1 each. 0 stands for a free square meter of the office room. 1 stands for an occupied square meter. It's guaranteed that at least one square meter in the room is free.

第一行包含两个以空格分隔的数字 nn 和 mm(1≤n,m≤251 \leq n, m \leq 25),表示办公室房间的尺寸。随后是 nn 行,每行包含 mm 个字符,每个字符为 0 或 1。0 表示办公室房间中一个空闲的平方米;1 表示一个被占用的平方米。保证房间中至少有一个平方米是空闲的。

输出格式

Output one number — the maximum possible perimeter of a bargaining table for Bob's office room.

输出一个数字——鲍勃办公室房间内议价桌可能的最大周长。

输入输出样例

  • 输入#1

    3 3
    000
    010
    000

    输出#1

    8
  • 输入#2

    5 4
    1100
    0000
    0000
    0000
    0000

    输出#2

    16

输入解题思路,AI测评打分。不知道怎么写?

首页