LeetCode 51. N皇后 / 52. N皇后 II（回溯）

示例:
输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

class Solution {
    vector<vector<string>> ans;
    int N;
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> map(n,string(n,'.'));
        N = n;
        dfs(map,0);
        return ans;
    }
    void dfs(vector<string>& map, int x)
    {
        if(x == N)
        {
            ans.push_back(map);
            return;
        }
        for(int i = 0; i < N; ++i)
        {
            if(isok(map,x,i))
            {
                map[x][i]='Q';
                dfs(map,x+1);
                map[x][i]='.';
            }
        }
    }
    bool isok(vector<string>& map, int i, int j)
    {
        int delta = 1;
        while(i-1 >= 0)
        {
            if(map[i-1][j]=='Q')//竖直方向
                return false;
            if(j-delta>=0 && map[i-1][j-delta]=='Q')
                return false;//左45度
            if(j+delta<N && map[i-1][j+delta]=='Q')
                return false;//右45度
            i--;//向上查找
            delta++;//45度增量
        }
        return true;
    }
};

class Solution {
    int sum = 0;
public:
    int totalNQueens(int n) {
        vector<string> map(n,string(n,'.'));
        for(int i = 0; i < n; ++i)
        {
            map[0][i]='Q';
            dfs(map,0,i,n);
            map[0][i]='.';
        }
        return sum;
    }

    bool isok(vector<string>& map, int x, int y, int &n)
    {
        int i = 1, j = y;
        while(x >= 1)//向上遍历，看冲突不
        {
            if(map[x-1][j]=='Q')//竖直方向
                return false;
            if(j-i>=0 && map[x-1][j-i]=='Q')//左45度
                return false;
            if(j+i<n && map[x-1][j+i]=='Q')//右45度
                return false;
            i++;//45度张角
            x--;//往上找
        }
        return true;
    }

    void dfs(vector<string>& map, int x, int y, int& n)
    {
        if(x==n-1)
            sum++;
        for(int i = 0; i < n; ++i)
        {   //x+1下一行
            if(x+1 < n && isok(map,x+1,i,n))
            {
                map[x+1][i] = 'Q';
                dfs(map, x+1, i, n);
                map[x+1][i] = '.';
            }
        }
    }
};