{"problem":{"name":"[信息与未来 2024] 间谍卫星","description":{"content":"Dr. X 研制的间谍卫星拍摄到了许多 U 国建筑的照片。为了找出其中的军事设施，Dr. X 需要估算建筑的大小。Dr. X 发现，所有间谍卫星拍摄的照片都恰好包含一个完整的正方形，其中建筑边界上的像素被标记为了白色（用 $1$ 表示），其余像素被标记为了黑色（用 $0$ 表示）。一些照片的案例如下： ![](https://cdn.luogu.com.cn/upload/image_hosti","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3980"},"statements":[{"statement_type":"Markdown","content":"Dr. X 研制的间谍卫星拍摄到了许多 U 国建筑的照片。为了找出其中的军事设施，Dr. X 需要估算建筑的大小。Dr. X 发现，所有间谍卫星拍摄的照片都恰好包含一个完整的正方形，其中建筑边界上的像素被标记为了白色（用 $1$ 表示），其余像素被标记为了黑色（用 $0$ 表示）。一些照片的案例如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5ponzg18.png)\n\n你的任务是根据拍摄的照片估算被摄正方形的**边长** (米)。照片中的每个像素都代表一个一米乘一米的正方形。\n\n## Input\n\n输入数据第一行包含一个整数 $n$，代表间谍卫星拍摄照片的数量，随后是 $n$ 张照片，其中每张照片 $128$ 行，每行 $128$ 个字符，$1$ 表示白色，$0$ 表示黑色。两张照片之间有一个空行。\n\n## Output\n\n为每张照片输出一个整数或小数，代表估计的正方形边长。输入数据保证每张照片中都恰好只包含一个正方形，且正方形的边界完全在照片内。\n\n[samples]\n\n## Note\n\n本题仅有一个 $n\\leq 100$ 的测试数据，且测试数据和样例数据的生成方式相同。\n\n当你对一幅照片估计的边长和实际建筑边长差距不超过 $2$ 时，则认为估计正确。若估计正确的照片比例 $A > 0.5$，本题得分为 $(A − 0.5) \\times 30$ 向下取整，否则得零分。\n\n我们在生成每张照片时，都先在平面上生成一个随机的、边长为整数、边界宽度为 $1$ 像素的正方形，然后“拍摄”得到它的照片。\n\n>本题原始满分为 $15\\text{pts}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3980","tags":["搜索","数学","2024","江苏","Special Judge","枚举","广度优先搜索 BFS","信息与未来"],"sample_group":[["见附件中的 sample.in","53"]],"created_at":"2026-03-03 11:09:25"}}