Day17-递归&回溯-N皇后

//
// Created by renyi on 2019/6/27.
//
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void LocationOccupiedByQueen(int x, int y, vector<vector<int>> &chess){//定义函数，求出第x行，第y列放置皇后之后，该皇后占用的位置，即8个方向的位置，占位用1表示
    static const int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};//单位方向数组，分别表示，上，下，左，右，左上，左下，右上，右下
    static const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
    chess[x][y] = 1;//皇后的位置，置1
    for (int i = 1; i < chess.size(); i++) {
        for (int j = 0; j < 8; j++) {//对8个方向的位置进行占位操作
            int new_x = x + i * dx[j];
            int new_y = y + i * dy[j];

            if (new_x >= 0 && new_x < chess.size() && new_y >= 0 && new_y < chess.size()){
                chess[new_x][new_y] = 1;
            }
        }
    }
}

//定义函数，k表示正在处理第k行的皇后，一共n列，location代表皇后的摆放位置，chess代表皇后的占位，result代表最终结果
void placeQueens(int k, int n, vector<string> &location, vector<vector<string>> &result, vector<vector<int>> &chess){
    if (k == n){//第n行下标n-1，已经处理到第n+1行，即都处理完了
        result.push_back(location);
        return;
    }

    for (int i = 0; i < n; i++) {//对于每一行的皇后，都有n列可能放置
        if (chess[k][i] == 0){
            vector<vector<int>> temp_chess = chess;//保存此时棋盘上皇后的占位情况，便于回溯至此
            location[k][i] = 'Q';//字符串数组location，皇后的位置放入Q
            LocationOccupiedByQueen(k, i, chess);//棋盘数组chess，将k行i列放入皇后
            placeQueens(k + 1, n, location, result, chess);//递归到下一行，依然有n列可能放入皇后
            chess = temp_chess;//递归回溯至此时，恢复当时的棋盘数组
            location[k][i] = '#';//将当前皇后位置重新置#号，再次尝试
        }
    }
}

//定义最终在main函数中调用的函数，NQueens，返回二维字符串数组
vector<vector<string>> NQueens(int n){//参数为n，n是几，就是几皇后
    vector<vector<string>> result;
    vector<string> location;
    vector<vector<int>> chess;

    for (int i = 0; i < n; i++) {
        chess.push_back((vector<int>()));//棋盘数组初始是n x n的0
        for (int j = 0; j < n; j++) {
            chess[i].push_back(0);
        }
        location.push_back("");
        location[i].append(n, '#');//在字符串末尾追加n个’#‘
    }
    placeQueens(0, n, location, result, chess);
    return result;
}

int main(){
    vector<vector<string>> result;
    result = NQueens(4);
    for (int i = 0; i < result.size(); i++) {
        printf("i = %d\n", i);
        for (int j = 0; j < result[i].size(); j++) {
            printf("%s\n", result[i][j].c_str());
        }
        printf("\n");
    }
    return 0;
}