[信息与未来 2024] 间谍卫星

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