NxN 矩阵涂色方案：深度优先搜索算法实现

给定一个 NxN 的矩阵 S，i 表示行，j 表示列，'#' 表示黑色，S i,j 是黑色，'.' 表示白色，S i,j 是白色。你需要选择 K 个白色的点将它们涂成红色，并且要求这 K 个红色的点必须连通，即每个红色点的上下左右至少相邻一个其他的红色点。问你一共有多少种涂色方案。

C++ 内容：可以使用深度优先搜索（DFS）来解决这个问题。

首先，我们定义一个二维数组 visited 来记录每个点是否已经被访问过。然后，我们遍历整个矩阵，对于每个白色点，我们将其涂成红色，并且将其标记为已访问。然后，我们从当前点开始进行深度优先搜索，搜索相邻的未访问的白色点，并将其涂成红色并标记为已访问。如果搜索过程中发现已经找到了 K 个红色点，则将结果加一。搜索完成后，将当前点恢复为白色并将其标记为未访问。

最后，返回结果即可。

以下是 C++ 的实现代码：

#include <iostream>
#include <vector>

using namespace std;

int n, k;
vector<vector<char>> matrix;
vector<vector<bool>> visited;
int result = 0;

void dfs(int x, int y, int count) {
    if (count == k) {
        result++;
        return;
    }

    visited[x][y] = true;

    if (x > 0 && matrix[x - 1][y] == '.' && !visited[x - 1][y]) {
        dfs(x - 1, y, count + 1);
    }

    if (x < n - 1 && matrix[x + 1][y] == '.' && !visited[x + 1][y]) {
        dfs(x + 1, y, count + 1);
    }

    if (y > 0 && matrix[x][y - 1] == '.' && !visited[x][y - 1]) {
        dfs(x, y - 1, count + 1);
    }

    if (y < n - 1 && matrix[x][y + 1] == '.' && !visited[x][y + 1]) {
        dfs(x, y + 1, count + 1);
    }

    visited[x][y] = false;
}

int main() {
    cin >> n >> k;

    matrix.resize(n, vector<char>(n));
    visited.resize(n, vector<bool>(n, false));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '.') {
                dfs(i, j, 1);
            }
        }
    }

    cout << result << endl;

    return 0;
}

希望对你有帮助！