leetcode练习题 n-queens

解题思路

深度搜索，用一个数组choose来标记每一行的摆放皇后的列，若row == n则存储结果，否则，在第row+1行放置皇后时，改行有n列，逐列放置皇后进行测试，检查与前面的行放置的皇后是否冲突，不冲突则进行下一行的摆放。处在同一列则冲突，斜线也冲突。

代码

#define MAXN 10001
class Solution {
public:void dfs(vector<vector<string>> &res,int row,int n){if(row == n){vector<string>cur;for(int i = 0;i < n;i++){string tmp = "";for(int j = 0;j < n;j++){if(j == choose[i])tmp += 'Q';elsetmp += '.';}cur.push_back(tmp);}res.push_back(cur);}else{for(int i = 0;i < n;i++){choose[row] = i;bool flag = true;for(int j = 0;j < row;j++){if(choose[j] == choose[row] || row - j == choose[j] - choose[row] || row - j == choose[row] - choose[j]){flag = false;break;}}if(flag == true)dfs(res,row + 1,n);}}}vector<vector<string> > solveNQueens(int n) {vector<vector<string>> res;memset(choose,-1,sizeof(choose));dfs(res,0,n);return res;}
};