007 画家问题 C语言解法

Question

用c语言，007:画家问题
查看提交统计提问
总时间限制: 1000ms 内存限制: 65536kB
描述
有一个正方形的墙，由N*N个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时，位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。

输入
第一行是一个整数n (1≤n ≤15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。
输出
一行，如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。
样例输入
5
wwwww
wwwww
wwwww
wwwww
wwwww
样例输出
15

Answer 1

下面给出一种可行的思路和对应的 C 语言示例代码。思路基于“第一行枚举+逐行确定”的经典方法，常见于类似“灯塔问题”(Lights Out) 的求解。主要区别在于题目只会翻转所涂格子“上下左右”四邻的颜色，而并不改变所涂格子本身的颜色。

核心思路

用 0/1 表示砖块颜色
- 可以约定：0 表示黄砖 (y)，1 表示白砖 (w)。目标是让整面墙都变成 0（黄）。
枚举第一行的涂法
- 由于第 1 行共有 n 个位置，每个位置可以选择“涂”或“不涂”，因此共有 $2^n$ 种可能。
- 对于每一种可能的“第一行涂法”，将其应用在一个“工作网格”上。
逐行“逼迫”下一行
- 应用完第一行后，从上到下依次查看每一行。如果发现上一行（例如第 i-1 行）有某个位置仍是 1（白），就必须在当前行（第 i 行）的相同列进行“涂刷”，以翻转上一行对应的位置，使其变成 0（黄）。
- 由于题目中“涂 (i,j)”只会翻转它的上下左右，所以“涂 (i,j)”恰好能翻转到 (i-1, j)，从而修正上一行的位置。
检验可行性与记录最优答案
- 当处理到最后一行后，如果最后一行还有 1（白），则说明该“第一行涂法”无法令所有砖变黄，放弃该方案。
- 若成功让最后一行全为 0（黄），记录当前所使用的“涂”次数（包括第一行和中间各行的涂刷），并更新最小值。
输出结果
- 如果所有 $2^n$ 种第一行方案都无法让整墙变黄，则输出 "inf"。
- 否则输出找到的最小涂刷次数。

该算法的主要耗时来自于要遍历 $2^n$ 种第一行情况。对每个情况，我们要进行大约 $O(n^2)$ 的操作。对于 $n \le 15$ ，在 C 语言里合理实现、注意一些细节后，一般可以在 1 秒左右运行通过。

示例代码

下面是一段示例 C 语言代码，演示如何实现上述思路。请根据实际需求进行输入输出格式调整。

c
#include <stdio.h>
#include <string.h>

#define MAXN 15
// 使用 grid[x][y] = 0 表示黄色(y)，1 表示白色(w)

int n;
int initGrid[MAXN][MAXN]; // 存储初始状态
int workGrid[MAXN][MAXN]; // 存储每次模拟时的工作状态

// 翻转某个格子的颜色：0->1, 1->0
void toggle(int x, int y) {
    workGrid[x][y] = 1 - workGrid[x][y];
}

// 在 (x, y) 处"涂画"，只会翻转其上下左右，不会翻转 (x, y) 本身
void paint(int x, int y) {
    if (x > 0)      toggle(x - 1, y); 
    if (x < n - 1)  toggle(x + 1, y);
    if (y > 0)      toggle(x, y - 1);
    if (y < n - 1)  toggle(x, y + 1);
}

// 计算给定“第一行涂法”时，需要的总涂画次数；若不能令所有格子变黄，则返回 -1
int calcPaintCount(int firstRowMask) {
    // 将初始状态拷贝到工作网格
    memcpy(workGrid, initGrid, sizeof(initGrid));

    int count = 0;

    // 先根据 firstRowMask 决定第一行哪些位置要涂
    for (int j = 0; j < n; j++) {
        // 检查第 j 位是否要涂
        if ((firstRowMask >> j) & 1) {
            paint(0, j);
            count++;
        }
    }

    // 从第二行开始，逐行“逼迫修正”上一行的白砖
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (workGrid[i - 1][j] == 1) {
                // 如果上一行 (i-1, j) 仍为白(1)，
                // 就必须在当前行 (i, j) 涂一次
                paint(i, j);
                count++;
            }
        }
    }

    // 检查最后一行是否全部为黄(0)
    for (int j = 0; j < n; j++) {
        if (workGrid[n - 1][j] == 1) {
            // 说明该方案无法令所有砖变黄
            return -1;
        }
    }

    // 能走到这里说明可以全部变黄，返回总涂画次数
    return count;
}

int main() {
    scanf("%d", &n);

    // 读取输入并存到 initGrid 中，用 0 表示 'y'，1 表示 'w'
    for (int i = 0; i < n; i++) {
        char row[MAXN+1];
        scanf("%s", row);
        for (int j = 0; j < n; j++) {
            if (row[j] == 'w') {
                initGrid[i][j] = 1;
            } else {
                initGrid[i][j] = 0;
            }
        }
    }

    // 枚举所有可能的第一行涂法
    int best = -1;
    int totalPatterns = 1 << n; // 2^n
    for (int mask = 0; mask < totalPatterns; mask++) {
        int res = calcPaintCount(mask);
        if (res >= 0) {
            if (best < 0 || res < best) {
                best = res;
            }
        }
    }

    if (best < 0) {
        printf("inf\n");
    } else {
        printf("%d\n", best);
    }

    return 0;
}

代码说明

initGrid[][]：用来存储最初的墙面颜色。
workGrid[][]：在每次测试不同第一行涂法时，用于模拟“涂画”操作的临时网格，初始时拷贝自 initGrid。
paint(x, y)：对 (x, y) 执行“涂画”，只会翻转其上下左右四个位置的颜色(越界则跳过)，不包含 (x, y) 本身。
calcPaintCount(firstRowMask)：给定一个“第一行”的涂画方案(用位掩码 firstRowMask 表示)，计算若以该方案开始，能否使全部砖变黄以及所需的涂画次数。
- 若无法将所有砖变黄，则返回 -1；
- 否则返回实际使用的涂画次数。
主函数中对所有 $2^n$ 种 firstRowMask 进行枚举，挑出能够成功的并且涂画次数最少的那个方案。

这样就可以得到最少需要涂画的砖数，若所有方案都无法将全部砖变黄，则输出 "inf"。

关于示例

题目样例：

text
n=5
wwwww
wwwww
wwwww
wwwww
wwwww

输出示例为 15，表示对于全白 5×5 的初始状态，这种“只翻转邻居”的规则下，最少需要涂 15 次才能全部变成黄色。该程序使用上述算法，也能够正确输出 15。

如需进一步优化(比如更快的运行速度)，可以考虑使用位运算、线性代数 (矩阵求解) 等方法对翻转过程进行更紧凑的表示，但对于 n ≤ 15，以上写法通常已经足够在题目限制的时间内通过。若 n 再大很多，则必须进一步进行更高级的优化或数学求解。

007 画家问题 C语言解法

سؤال

الفكرة

الإجابة

核心思路

示例代码

代码说明

关于示例

مشاركة هذا السؤال والجواب