题目描述

填字游戏可以用一个 $m\times n$ 的 $0$ 和 $1$ 矩阵来表示。$0$ 表示白色方格，$1$ 表示黑色方格。某些白色方格需要编号，这些编号用于标记单词描述（横向或纵向）的起始位置。

一个方格被编号的条件是：

• 它是白色方格，并且满足以下条件之一：
  • ($\text{a}$) 下方方格是白色，且上方没有白色方格（即该白色方格是一列白色方格的顶部）
  • ($\text{b}$) 左侧没有白色方格，且右侧方格是白色（即该白色方格是一行白色方格的左端）

方格按照从左到右、从上到下的顺序编号。

从矩阵可以绘制出填字游戏图。图中每个方格用一个 $4\times 6$ 字符的框表示。黑色方格和白色方格（有编号和无编号）的表示方式如下（其中 $\text{nnn}$ 是方格的编号）：

++++++
+    +
+    +
++++++

对于有编号的白色方格，编号显示在框的左上角区域：

+001 +
+    +
+    +
++++++

框的其余字符为空格。如果边缘的黑色方格应该从图中移除（见样例输出）。只使用必要的填充字符，不要在一行末尾添加不必要的空格。

输入格式

输入文件由多个数据块组成，每个数据块描述一个填字游戏。每个数据块的第一行包含两个整数 $m<25$ 和 $n<25$，以空格分隔。接下来的 $m$ 行，每行有 $n$ 个数字 $0$ 或 $1$，以空格分隔。最后一个数据块为空，$m=n=0$。

输出格式

输出文件包含除最后一个数据块外每个数据块对应的填字游戏图。每个图后输出一个空行。

样例输入

6 7
1 0 0 0 0 1 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 1 0 0 1 1 1
0 0 0 1 0 0 0
1 0 0 0 0 0 1
5 3
1 0 1
0 0 0
1 1 1
0 0 0
1 0 1
0 0

样例输出

++++++++++++++++++++++
+001 +002 +003 +    +
+    +    +    +    +
++++++++++++++++++++++
+    +    +004 +    +
+    +    +    +    +
++++++++++++++++++++++
+    +    +    +    +
+    +    +    +    +
++++++++++++++++++++++

---

题目分析

问题的本质

这是一个填字游戏可视化问题。给定一个 $0/1$ 矩阵（$0$ 白色，$1$ 黑色），需要：

1. 根据规则为白色方格编号
2. 去除边缘的黑色方格（不需要显示）
3. 将每个方格绘制为 $4\times 6$ 字符的框
4. 在编号方格的左上角显示三位编号

关键要点

• 编号规则：顶部或左侧是边界或黑色方格的白色方格
• 边缘黑色方格不显示：一个黑色方格如果位于矩阵边缘且其“外侧”没有白色方格，则被移除
• 绘图：每个方格 $4$ 行高、$6$ 列宽
• 编号显示：三位数字，不足三位时高位补零

编号规则详解

一个白色方格 $(i,j)$（从 $1$ 开始索引）需要编号的条件：

条件 (a)：垂直方向是单词的起始

• 下方方格是白色（$i<m$ 且 $grid[i+1][j]=0$）
• 上方没有白色方格（$i=1$ 或 $grid[i-1][j]=1$）

条件 (b)：水平方向是单词的起始

• 右侧方格是白色（$j<n$ 且 $grid[i][j+1]=0$）
• 左侧没有白色方格（$j=1$ 或 $grid[i][j-1]=1$）

满足任一条件即可编号。

边缘黑色方格的处理

题目要求：“如果黑色方格在边缘，应该从图中移除”。这意味着：

• 如果一个黑色方格位于矩阵的边界（第一行、最后一行、第一列、最后一列）
• 且它的“外侧”方向没有白色方格（即它在矩阵外部没有相邻的白色区域）
• 则该黑色方格不应该出现在最终绘图中

更精确地说：如果一个黑色方格可以通过连续相邻的黑色方格到达边界，那么它应该被移除（不绘制）。这可以通过洪水填充（$\text{flood fill}$）实现：

1. 从所有边界上的黑色方格出发进行 $\text{DFS}$ 或 $\text{BFS}$
2. 标记所有可达的黑色方格（这些是“边缘”黑色方格）
3. 剩余的黑色方格是“内部”黑色方格，需要绘制

---

解题思路

步骤一：读取矩阵

使用基于 $1$ 的索引存储矩阵，便于处理边界条件。

步骤二：标记边缘黑色方格

使用 $\text{DFS}$ 从边界上的黑色方格开始：

void floodFill(int x, int y) {
    if (x >= 1 && x <= m && y >= 1 && y <= n)
        if (grid[x][y] == 1) {
            grid[x][y] = -3;  // 标记为边缘黑色方格
            for (int i = 0; i < 4; i++)
                floodFill(x + offset[i][0], y + offset[i][1]);
        }
}

遍历所有边界方格，如果是黑色，则调用 floodFill。

步骤三：标记内部黑色方格

剩余的黑色方格（值为 $1$）是内部黑色方格，标记为 $-1$。

步骤四：编号白色方格

遍历所有白色方格（值为 $0$），检查编号条件。符合条件的方格赋值为递增的编号（从 $1$ 开始）。

步骤五：处理边缘黑色方格的显示

有些边缘黑色方格（标记为 $-3$）在最终绘图中可能仍然需要显示，这取决于它们是否与白色方格相邻。

具体处理：从右向左扫描每一行，如果该行右侧有白色方格（编号$\ge 0$），则标记该行中右侧的黑色方格为需要显示（$-2$）。

for (int i = 1; i <= m; i++) {
    bool solidAtRight = false;
    for (int j = n; j >= 1; j--) {
        if (grid[i][j] >= 0) solidAtRight = true;
        else if (grid[i][j] == -3 && solidAtRight) grid[i][j] = -2;
    }
}

步骤六：绘制方格

每个方格在屏幕上占据 $4$ 行高、$6$ 列宽。

• 黑色方格（$-1$）：全部填充 +
• 边缘黑色方格（$-2$）：全部填充空格（不显示）
• 白色方格（$\ge 0$）：边框为 +，内部为空格；如果有编号，在左上角显示三位数字

绘制时的坐标计算：

• 行坐标：row = (i-1) * 3
• 列坐标：column = (j-1) * 5

因为每个方格占 $4$ 行，但方格之间垂直方向相邻（共享边框），所以每处理一行方格，row 增加 $3$（而不是 $4$）。

步骤七：输出

输出 screen 数组中所有非零字符。每行结束后输出换行。每个数据块结束后输出一个空行。

---

算法复杂度分析

时间复杂度

• 矩阵大小：$m\times n\le 25\times 25=625$
• 洪水填充：$O(m\times n)$
• 编号：$O(m\times n)$
• 绘制：$O(m\times n)$，每个方格绘制 $4\times 6=24$ 个字符
• 总复杂度：$O(m\times n)$，完全可行

空间复杂度

• 矩阵存储：$O(m\times n)$
• 屏幕字符数组：$90\times 180=16200$，足够大

---

正确性证明

引理 1：洪水填充正确标记了所有与边界相连的黑色方格。

证明：从边界黑色方格出发，沿着相邻黑色方格进行 $\text{DFS}$，可以访问所有连通分量中的黑色方格。$\square$

引理 2：编号规则正确标识了横向或纵向单词的起始位置。

证明：条件 (a) 确保该方格是垂直方向的第一个白色方格（上方是边界或黑色）；条件 (b) 确保该方格是水平方向的第一个白色方格（左方是边界或黑色）。$\square$

引理 3：边缘黑色方格的显示规则正确。

证明：如果一个黑色方格在边缘且其右侧有白色方格，那么它在绘图中应该显示（因为它与白色区域相邻）；否则不显示。$\square$

---

参考代码

// Crosswords (II)
// UVa ID: 312
// Verdict: Accepted
// Submission Date: 2016-07-06
// UVa Run Time: 0.040s
//
// 版权所有（C）2016，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

int m, n, grid[30][30];          // 原始网格，-3:边缘黑色，-2:需显示黑色，-1:内部黑色
char screen[90][180];            // 屏幕字符数组
int offset[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

// 洪水填充：标记所有与边界相连的黑色方格
void floodFill(int x, int y)
{
    if (x >= 1 && x <= m && y >= 1 && y <= n)
        if (grid[x][y] == 1)
        {
            grid[x][y] = -3;     // 标记为边缘黑色
            for (int i = 0; i < 4; i++)
                floodFill(x + offset[i][0], y + offset[i][1]);
        }
}

int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);

    while (cin >> m >> n, m && n)
    {
        // 读取矩阵
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                cin >> grid[i][j];
        
        // 标记所有与边界相连的黑色方格（边缘黑色）
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (i == 1 || i == m || j == 1 || j == n)
                    if (grid[i][j] == 1)
                        floodFill(i, j);
        
        // 剩余的黑色方格是内部黑色，标记为 -1
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (grid[i][j] == 1)
                    grid[i][j] = -1;
        
        // 白色方格编号
        int number = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (grid[i][j] == 0 &&
                    (((j == 1 || grid[i][j - 1] < 0) && (j < n && grid[i][j + 1] >= 0)) ||
                     ((i < m && grid[i + 1][j] >= 0) && (i == 1 || grid[i - 1][j] < 0))))
                    grid[i][j] = number++;  // 分配编号
        
        // 处理边缘黑色方格的显示：如果右侧有白色方格，则显示
        for (int i = 1; i <= m; i++)
        {
            bool solidAtRight = false;
            for (int j = n; j >= 1; j--)
            {
                if (grid[i][j] >= 0) solidAtRight = true;
                else if (grid[i][j] == -3 && solidAtRight) grid[i][j] = -2;  // 需要显示
            }
        }
        
        // 初始化屏幕数组
        memset(screen, 0, sizeof(screen));
        
        // 绘制每个方格
        int row = 0;  
        for (int i = 1; i <= m; i++)
        {
            int column = 0;
            for (int j = 1; j <= n; j++)
            {
                if (grid[i][j] == -2)
                {
                    // 不显示的边缘黑色：填充空格
                    for (int x = 0; x < 4; x++)
                        for (int y = 0; y < 6; y++)
                            if (screen[row + x][column + y] == 0)
                                screen[row + x][column + y] = ' ';
                }
                else if (grid[i][j] == -1)
                {
                    // 内部黑色：全部填充 +
                    for (int x = 0; x < 4; x++)
                        for (int y = 0; y < 6; y++)
                            screen[row + x][column + y] = '+';
                }
                else if (grid[i][j] >= 0)
                {
                    // 白色方格：绘制边框和内部
                    for (int x = 0; x < 4; x++)
                        for (int y = 0; y < 6; y++)
                        {
                            if (x == 0 || x == 3 || y == 0 || y == 5)
                                screen[row + x][column + y] = '+';  // 边框
                            else
                                screen[row + x][column + y] = ' ';  // 内部
                        }
                    
                    // 显示编号（三位数字）
                    if (grid[i][j] > 0)
                    {
                        screen[row + 1][column + 1] = grid[i][j] / 100 + '0';
                        screen[row + 1][column + 2] = (grid[i][j] % 100) / 10 + '0';
                        screen[row + 1][column + 3] = grid[i][j] % 10 + '0';
                    }
                }
                
                column += 5;  // 每格宽6，但边框共享，所以水平移动5
            }
            
            row += 3;  // 每格高4，但边框共享，所以垂直移动3
        }
        
        // 输出结果
        for (int i = 0; i <= m * 3; i++)
        {
            for (int j = 0; j <= n * 5; j++)
                if (screen[i][j] > 0)
                    cout << screen[i][j];
            cout << endl;
        }
        
        cout << endl;  // 每个数据块后空行
    }
    
    return 0;
}

---

总结

本题的核心在于：

1. 洪水填充：标记与边界相连的黑色方格
2. 编号规则：识别横向或纵向单词的起始位置
3. 边缘处理：确定哪些边缘黑色方格需要显示
4. 精确绘图：每个方格 $4\times 6$，边框共享

关键点回顾

知识点	说明
矩阵表示	$0$ 白色，$1$ 黑色
编号条件	顶部/左侧为边界或黑色
边缘黑色	洪水填充标记
内部黑色	全部显示
绘图尺寸	每格 $4$ 行 × $6$ 列
边框共享	相邻方格共用边框

绘图坐标计算

• 水平方向：每个方格占 $6$ 列，但边框重叠，所以索引间隔 $5$
• 垂直方向：每个方格占 $4$ 行，但边框重叠，所以索引间隔 $3$

这种“边框共享”的设计使得相邻方格的边框连续，形成一个完整的网格。