为了求解该问题，我们需要判断是否可以通过一系列操作将矩阵变为全黑，并求出最少操作次数。以下是详细的解题思路和代码实现。

解题思路

1. 必要条件检查：

   • 每一列必须至少有一个黑色（#），否则无法填充该列（因为填充列需要某一行在操作时是全黑的，而若某列全白，则无法通过任何操作使其变为全黑）。
   • 如果存在某一列全白（即无 #），直接输出 -1。

2. 计算全黑列的数量：

   • 统计初始矩阵中全黑的列（即列中所有元素均为 #）的数量 full_columns。

3. 检查是否存在全黑行：

   • 若存在至少一行是全黑的，则可以利用该行快速填充其他列。此时，最少操作次数为 n - full_columns（即用全黑行填充 n - full_columns 个非全黑列）。

4. 若不存在全黑行：

   • 需要先通过操作使某一行变为全黑。对于每一行，计算其白色单元格（.）的数量 white_count。
   • 选择白色单元格最少的行，将其变为全黑需要 min_white 次操作（每次操作将该行复制到一个白色单元格所在的列）。
   • 然后，用该行填充剩余的 n - full_columns 个非全黑列。
   • 总操作次数为 min_white + (n - full_columns)。

代码实现

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    // 检查每列是否至少有一个 '#'
    for (int j = 0; j < n; j++) {
        bool has_black = false;
        for (int i = 0; i < n; i++) {
            if (grid[i][j] == '#') {
                has_black = true;
                break;
            }
        }
        if (!has_black) {
            cout << -1 << endl;
            return 0;
        }
    }

    int full_columns = 0;
    for (int j = 0; j < n; j++) {
        bool is_full = true;
        for (int i = 0; i < n; i++) {
            if (grid[i][j] != '#') {
                is_full = false;
                break;
            }
        }
        if (is_full) {
            full_columns++;
        }
    }

    bool has_full_row = false;
    for (int i = 0; i < n; i++) {
        bool is_full = true;
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != '#') {
                is_full = false;
                break;
            }
        }
        if (is_full) {
            has_full_row = true;
            break;
        }
    }

    if (has_full_row) {
        cout << n - full_columns << endl;
    } else {
        int min_white = INT_MAX;
        for (int i = 0; i < n; i++) {
            int white_count = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '.') {
                    white_count++;
                }
            }
            if (white_count < min_white) {
                min_white = white_count;
            }
        }
        cout << min_white + (n - full_columns) << endl;
    }

    return 0;
}

关键点说明

• 列检查：确保每列至少有一个 #，否则无法完成目标。
• 全黑列统计：统计初始全黑列的数量，用于后续计算。
• 全黑行检查：若存在全黑行，可直接用其填充非全黑列，操作次数为 n - full_columns。
• 最小白色行：若无全黑行，选择白色单元格最少的行，使其变为全黑，再用该行填充其他列。

时间复杂度

• 时间复杂度：$O(n^2)$，因为需要遍历矩阵两次（检查列、统计全黑列、检查全黑行、统计白色单元格）。
• 空间复杂度：$O(n^2)$，用于存储矩阵。

示例验证

样例 1

输入：

2
#.
.#

输出：3
解释：没有全黑行，每行有 1 个白色单元格，n - full_columns = 2 - 0 = 2，总操作数为 1 + 2 = 3。

样例 2

输入：

2
..
..

输出：-1
解释：两列全白，无法填充。

总结

本题通过合理利用矩阵的列和行属性，结合贪心策略，高效地求解了最少操作次数。核心在于判断是否存在全黑行以及选择最优行进行操作，确保在满足条件的前提下达到最优解。