草根妖怪网络科技有限公司正委托河童重工架设若干个基站。 架设地点可以抽象成一个 n * n 的方格阵。每个基站提供信号的范围是其临近的上下左右四格（如果存在） 为了避免资源浪费，需要保证对于任意一个基站，其所在方格不存在其他基站的信号。通俗点讲，就是不能将基站布置在已有其他基站信号覆盖的地方。满足该要求的基站布局方案被成为合法的，反之为不合法的。 下面是两个例子： 左图的布局是合法的，而右图的两个基站的信号互相覆盖到了另一个基站，因此是不合法的 (注意：什么都不放也是一个合法的布局方式) 现在，河童重工的工程师荷城荷取要求你帮她算出，在这样一个 n * n 的方格阵中，有多少种不同的合法的布局方案。用c++实现

一种解法是使用回溯法，从左上角开始遍历格子，对于每个格子，如果能放置基站，则放置并继续往下遍历；如果不能放置，就跳过该格子；当遍历到右下角时，如果所有基站都放置完毕，则记录一种合法方案。

具体实现：

#include <iostream>
#include <vector>

using namespace std;

bool check(vector<vector<int>>& grid, int x, int y) {
    // 检查上下左右四个方向是否有基站
    if (x > 0 && grid[x-1][y] == 1) return false;
    if (x < grid.size()-1 && grid[x+1][y] == 1) return false;
    if (y > 0 && grid[x][y-1] == 1) return false;
    if (y < grid[0].size()-1 && grid[x][y+1] == 1) return false;
    return true;
}

void backtrack(vector<vector<int>>& grid, int x, int y, int& count, int k) {
    if (x == grid.size()) { // 遍历完所有格子
        if (k == 0) count++; // 所有基站都放置完毕，则记录合法方案
        return;
    }
    int nx = (y == grid[0].size()-1 ? x+1 : x); // 计算下一个格子的坐标
    int ny = (y == grid[0].size()-1 ? 0 : y+1);
    if (k > 0 && check(grid, x, y)) { // 当前格子可以放置基站
        grid[x][y] = 1;
        backtrack(grid, nx, ny, count, k-1); // 往下遍历，并减少一个基站
        grid[x][y] = 0; // 回溯
    }
    backtrack(grid, nx, ny, count, k); // 当前格子不能放置基站，直接往下遍历
}

int countLegalLayouts(int n, int k) {
    vector<vector<int>> grid(n, vector<int>(n));
    int count = 0;
    backtrack(grid, 0, 0, count, k); // 从左上角开始遍历
    return count;
}

int main() {
    int n = 4, k = 2;
    cout << countLegalLayouts(n, k) << endl; // 输出合法方案数
    return 0;
}

该算法的时间复杂度为 $O(2^{n^2})$，因为每个格子都有两种状态（放置或不放置基站），总共有 $n^2$ 个格子。在 $n$ 较小的情况下可以接受，但是当 $n$ 较大时，需要使用其他算法进行优化。