折腾折腾，发现最近做的几道dfs题目似乎是同一个思想：把一堆东西塞到某一个新的地方
    所以需要考虑的是塞还是不塞，如果塞塞哪一个，要塞到哪一个位置里面去

    这道题按照这个思路就是有n个棋子，想要塞到一个n*n的棋盘里面去
    要怎么遍历这个棋盘呢？一个格子一个格子遍历？ 一行一行遍历？ 一列一列遍历？
    如果按照一个格子一个格子遍历：
    那么来到一个格子，我是放棋子进去还是不放进去

    1. class Solution {
    2.     vector<vector<string>> res;
    3.     int n;
    4.     void dfs(vector<bool>& col, vector<bool>& dig, vector<bool>& udig, vector<string>& v, int rownum)
    5.     {
    6.         if(rownum == n)
    7.         {
    8.             res.push_back(v);
    9.             return;
    10.         }
    11.         for(int j = 0; j < n; j++)
    12.         {
    13.             if(col[j] || dig[j - rownum + n] || udig[j + rownum])
    14.                 continue;
    15.             v[rownum][j] = 'Q';
    16.             col[j] = dig[j - rownum + n] = udig[j + rownum] = true;
    17.             dfs(col, dig, udig, v, rownum + 1);
    18.             col[j] = dig[j - rownum + n] = udig[j + rownum] = false;
    19.             v[rownum][j] = '.';
    20.         }
    21.     }
    24. public:
    25.     vector<vector<string>> solveNQueens(int _n) {
    26.         n = _n;
    27.         //这里2*n的原因：想一下棋盘是关于对角线对称的，一侧是有n个，另外一侧也是n个，去掉中间的重复算就是2n - 1
    28.         //row是记录行被用过没有，col是记录列被用过没有，dig是记录y = x对角线被用过没有，udig是记录y = -x对角线被用过没有
    29.         int N = 2*n;
    30.         vector<bool> row(n, false);
    31.         vector<bool> col(n,false), dig(N, false), udig(N, false);
    32.         //还有一点是关于行列以及对角线的对应关系
    33.         //x,y对应的y = x + b对角线是n + (y - x), y = -x + b对角线是 y + x
    34.         vector<string> v(n, string(n, '.'));
    35.         dfs(col, dig, udig, v, 0);
    36.         return res;
    37.     }
    38. };

    如果按照行遍历：
    这一行我是放哪一个格子里面去？

    class Solution {
    vector<vector<string>> res;
    int n;
    void dfs(vector<bool>& row,vector<bool>& col,vector<bool>& dig,vector<bool>& udig,vector<string>& v,int rowidx,int colidx,int cnt)
    {
        if(cnt == n)
        {
            res.push_back(v);
            return;
        }
        if(colidx == n)
        {
            rowidx++;
            colidx = 0;
        }
        if(rowidx == n)
            return;
        dfs(row, col, dig, udig, v, rowidx, colidx+1, cnt);
        if(!row[rowidx] && !col[colidx] && !dig[n + colidx - rowidx] && !udig[colidx + rowidx])
        {
            v[rowidx][colidx] = 'Q';
            row[rowidx] = col[colidx] = dig[n + colidx - rowidx] = udig[colidx + rowidx] = true;
            dfs(row, col, dig, udig, v, rowidx, colidx + 1, cnt + 1);
            row[rowidx] = col[colidx] = dig[n + colidx - rowidx] = udig[colidx + rowidx] = false;
            v[rowidx][colidx] = '.';          
        }          
    }
public:
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;

        vector<string> v = vector(n, string(n, '.'));
        vector<bool> row(n, false), col(n, false), dig(2*n, false), udig(2*n, false);
        dfs(row, col, dig, udig, v, 0, 0, 0);
        return res;
    }
};

    第二次写题

    class Solution {
    vector<vector<string>> res;
    vector<bool> rows;
    vector<bool> cols;
    vector<bool> diag;
    vector<bool> udiag;
    vector<string> board;
    int n;
    void dfs(int x, int y, int remain)
    {
        if(remain == 0)
        {
            res.push_back(board);
            return;
        }  
        if(y == n)
        {
            x++;
            y = 0;
        }
        if(x == n) return;
        // cout << x << ' ' << y << endl;
        if(rows[x] && cols[y] && diag[y - x + n] && udiag[y + x] && board[x][y] == '.')
        {
            board[x][y] = 'Q';
            rows[x] = cols[y] = false;
            diag[y - x + n] = udiag[y + x] = false;
            dfs(x, y + 1, remain - 1);
            board[x][y] = '.';
            rows[x] = cols[y] = true;
            diag[y - x + n] = udiag[y + x] = true;
        }
        dfs(x, y + 1, remain);
    }
public:
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        rows = vector<bool>(n, true);
        cols = vector<bool>(n, true);
        diag = vector<bool>(2*n, true);
        udiag = vector<bool>(2*n, true);
        board = vector<string>(n, string(n, '.'));
        dfs(0, 0, n);
        return res;
    }

};

    class Solution {
    vector<bool> cols;
    vector<bool> diag;
    vector<bool> udiag;
    vector<vector<string>> res;
    vector<string> path;
    int n;
    void dfs(int row)
    {
        if(row == n)
        {
            res.push_back(path);
            return;
        }
        for(int j = 0; j < n; j++)
        {
            if(cols[j] == false || diag[j - row + n] == false || udiag[j + row] == false) continue;
            cols[j] = diag[j - row + n] = udiag[j + row] = false;
            path[row][j] = 'Q';
            dfs(row + 1);
            cols[j] = diag[j - row + n] = udiag[j + row] = true;
            path[row][j] = '.';
        }
    }
public:
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        cols = vector<bool>(n, true);
        diag = vector<bool>(2*n, true);
        udiag = vector<bool>(2*n, true);
        path = vector<string>(n, string(n, '.'));
        dfs(0);
        return res;
    }
};