非遗纹样修复：残片展板最大连片统计

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：8
• 训练题主题：非遗纹样修复：残片展板最大连片统计
• 所属赛道：非遗文化赛道

题目背景

纹样修复课会先把残片分布数字化成 0/1 展板，其中 1 表示可修复纹样残片。老师希望快速知道共有多少片连通残片、最大连片有多大，以及最大连片中坐标最小的代表格子。

任务描述

• 读取 0/1 网格并按上下左右四方向统计连通块。
• 输出连通块数量和最大连片面积。
• 若最大面积相同，输出代表坐标字典序最小的连片起点。

输入格式

1. 第一行输入 r c，表示网格行列数。
2. 接下来输入 r 行长度为 c 的字符串，只包含 0 和 1。

输出格式

1. 第一行输出 components=连通块个数。
2. 第二行输出 largest=最大连片面积。
3. 第三行输出 best_origin=行 列。

数据范围与说明

• 1 <= r, c <= 200。
• 仅按上下左右四方向连通。
• 若没有任何 1，输出 components=0、largest=0、best_origin=0 0。
• 若最大面积相同，取连片中最小坐标也最小的那一块。

样例输入

4 5
11000
01011
00111
10000

样例输出

components=3
largest=5
best_origin=2 4

样例解释

• 共有三块互不连通的残片区域，因此 components=3。
• 右侧区域面积最大，共有 5 个格子。
• 该最大区域中坐标最小的格子是第 2 行第 4 列，所以 best_origin=2 4。

知识点清单

• 二维数组遍历。
• 访问标记的使用。
• BFS / DFS 连通块搜索。
• 连通块面积累计。
• 坐标并列比较规则。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= r, c <= 200。
• 仅按上下左右四方向连通。
• 若没有任何 1，输出 components=0、largest=0、best_origin=0 0。
• 若最大面积相同，取连片中最小坐标也最小的那一块。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 网格 BFS 连通块搜索 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 网格中没有任何 1 时，最佳坐标必须输出 0 0。
• 多个最大连通块面积相同时，要比较代表坐标的字典序。
• 边界格子只有部分方向可扩展，不能越界访问。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：exact
• 主算法：网格 BFS 连通块搜索

判题重点

• 重点校验公式、排序规则和格式化输出是否完全一致。
• 隐藏数据会覆盖边界值、重复值和最小规模输入。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 准备整张网格全为 0 和全为 1 的用例。
• 准备多个最大连通块并列的用例，检查坐标比较逻辑。
• 准备单行、单列网格，验证边界扩展。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

4 5
11000
01011
00111
10000

样例输出：sample.out

components=3
largest=5
best_origin=2 4

题解、建模与最终解法

自动整理的解题流程

• 题目主题：非遗纹样修复：残片展板最大连片统计
• 题目摘要：在 0/1 网格中统计连通块数量、最大连片面积和最佳代表坐标。
• 判题提示：该题以精确输出为主，最终程序需要重点保证公式、顺序和格式完全一致。
• 把原始记录转成统一结构后再做合法性校验、去重、编码还原或标准化输出。
• 优先定义好字段映射和异常输入处理策略。

解题思路

源文件：solution-rationale.md

1. 问题重述

在 0/1 网格中统计连通块数量、最大连片面积和最佳代表坐标。

2. 数据结构与建模

• 主算法：网格 BFS 连通块搜索
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 从每个未访问且值为 1 的格子出发，启动一次 BFS。
2. 在 BFS 过程中累计当前连通块面积，并记录其中坐标最小的格子。
3. 每完成一个连通块，就更新总连通块数和最佳答案。
4. 全部扫描结束后统一输出结果。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 网格中没有任何 1 时，最佳坐标必须输出 0 0。
• 多个最大连通块面积相同时，要比较代表坐标的字典序。
• 边界格子只有部分方向可扩展，不能越界访问。

7. 知识点清单

• 二维数组遍历。
• 访问标记的使用。
• BFS / DFS 连通块搜索。
• 连通块面积累计。
• 坐标并列比较规则。

设计决策记录

源文件：decision-log.md

• 选择 网格 BFS 连通块搜索 作为主算法，因为它能直接覆盖题目的核心约束。
• 题目是标准网格连通块统计，BFS 和 DFS 都能胜任。
• 为了便于稳定处理大网格，主实现选择显式队列的 BFS。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备整张网格全为 0 和全为 1 的用例。
• 准备多个最大连通块并列的用例，检查坐标比较逻辑。
• 准备单行、单列网格，验证边界扩展。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

from collections import deque
import sys


def solve(data: str) -> str:
    raw_lines = [line.strip() for line in data.splitlines() if line.strip()]
    if not raw_lines:
        return ""
    rows, cols = map(int, raw_lines[0].split())
    grid = raw_lines[1:1 + rows]
    visited = [[False] * cols for _ in range(rows)]
    components = 0
    best_area = 0
    best_origin = (0, 0)
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != "1" or visited[row][col]:
                continue
            components += 1
            queue = deque([(row, col)])
            visited[row][col] = True
            area = 0
            origin = (row + 1, col + 1)
            while queue:
                cur_row, cur_col = queue.popleft()
                area += 1
                cur_origin = (cur_row + 1, cur_col + 1)
                if cur_origin < origin:
                    origin = cur_origin
                for dr, dc in directions:
                    nxt_row = cur_row + dr
                    nxt_col = cur_col + dc
                    if not (0 <= nxt_row < rows and 0 <= nxt_col < cols):
                        continue
                    if visited[nxt_row][nxt_col] or grid[nxt_row][nxt_col] != "1":
                        continue
                    visited[nxt_row][nxt_col] = True
                    queue.append((nxt_row, nxt_col))
            if area > best_area or (area == best_area and origin < best_origin):
                best_area = area
                best_origin = origin
    return "\n".join(
        [
            f"components={components}",
            f"largest={best_area}",
            f"best_origin={best_origin[0]} {best_origin[1]}",
        ]
    )


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

代码执行与运行结果

最新成功运行

PY 运行输出摘录

components=3
largest=5
best_origin=2 4

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s1-jh-07-heritage-pattern-grid/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s1-jh-07-heritage-pattern-grid/02-solution
• 运行证据：10-cases/s1-jh-07-heritage-pattern-grid/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md

• 完整解题档案：complete-solution-dossier.md
• 代码附录：appendix-code.md
• 运行附录：appendix-runs.md

题目概述

在 0/1 网格中统计连通块数量、最大连片面积和最佳代表坐标。

最终解法摘要

自动整理的解题流程

• 题目主题：非遗纹样修复：残片展板最大连片统计
• 题目摘要：在 0/1 网格中统计连通块数量、最大连片面积和最佳代表坐标。
• 判题提示：该题以精确输出为主，最终程序需要重点保证公式、顺序和格式完全一致。
• 把原始记录转成统一结构后再做合法性校验、去重、编码还原或标准化输出。
• 优先定义好字段映射和异常输入处理策略。

代码执行摘要

交付说明

本报告为摘要版，详细题目、题干、题解、最终代码、运行结果和调试流程已经汇总到完整解题档案中。