[AHOI2007]红十字

www.rqnoj.cn/Problem_300.html

题目:[AHOI2007]红十字

问题编号:300

题目描述

通往藏宝库的通道打开了,走下一段长长的楼梯,钻过一条矮矮的地道,你和小可可终于来到了藏宝库的门前。随之而来的就是最后一 个挑战,只要能打开宝库的门,里面的宝藏就是你们的了。
宝库的门依然是通过机关打开,这个门很奇怪,是一个正方形,被划分成许多大小一致的正方形 的小方格,这些方格不是红色就是白色,猛看上去这些方格组成了许多红十字状的标志。根据藏宝图记载,只要找到门上最大的红十字,按下它中心的方格,宝库的 门就能打开了。
红十字标志也是一个正方形,边长为(2k+1)*(2k+1),其中k为非负整数。它的四条边与门的边平行,而且恰由门上的 (2k+1)*(2k+1)个小方格组成。这里,红十字标志是以白色为底色,红色为十字的颜色。假设用1表示红色,用0表示白色。对应到计算机处理的数据 中,就是除了正中列与正中行全为1外,其余方格均为0。以下是几种不同大小的标志:
1*1:
1
3*3
010
111
010
5*5
00100
00100
11111
00100
00100

小 可可被这个机关难到了,现在只有靠你了,请你帮助他在这个门上找到一个最大的红十字标志,输出它的边长即可。

输入格式

输入文件中第一行有一个整数n(1<=n<=2,000),表示门由n个方格组成。
以下n行,每行n个字 符,每个字符都是0或1。数据中不会出现全为0的情况。

输出格式

输出一个数,即最大的红十字标志的边长。

样例输入 5 00011 01011 11100 01001 00010 样例输出 3 三维状态图像
这道题挺有意思啊,首先求出每个点从4个方向最多按1能延伸多少,还有从四个方向开上的最大全为0正方形。。时限太紧了。。代码写的我要吐了。。我不得已只好用了指针。。ugly Code….
Code:
www.ideone.com/gXeXg

One thought on “[AHOI2007]红十字

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>