leetcode：N-Queens （n皇后有关问题） 【面试算法题】

leetcode：N-Queens （n皇后问题） 【面试算法题】

题目：The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[ [".Q..",  // Solution 1  "...Q",  "Q...",  "..Q."], ["..Q.",  // Solution 2  "Q...",  "...Q",  ".Q.."]]

dfs去遍历，考虑所有可能，row中记录每一行棋子的位置，col记录当前列是否有棋子，对角线的判断就是两点行差值和列差值是否相同。

当dfs深度达到n时，就表示存在满足条件的解，把当前状态图存到结果中。

temp（n, '.'）先把字符串全部赋值成 ‘ . ' ，在吧存在棋子的位置改成’Q‘

int row[1000];    int col[1000];    vector<vector<string> >result;class Solution {public:    void dfs(int r,int n)    {        int i,j;        if(r==n)        {            vector<string>go;            for(i=0;i<n;++i)            {                string temp(n,'.');                temp[row[i]]='Q';                go.push_back(temp);            }            result.push_back(go);        }        for(i=0;i<n;++i)        {            if(col[i]==0)            {                for(j=0;j<r;++j)                    if(abs(j-r)==abs(i-row[j]))break;                if(j==r)                {                    row[r]=i;                    col[i]=1;                    dfs(r+1,n);                    col[i]=0;                    row[r]=0;                }            }        }            }    vector<vector<string> > solveNQueens(int n) {        result.clear();        dfs(0,n);        return result;    }};//      blog.csdn.net/havenoidea