51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n?皇后问题?研究的是如何将?n?个皇后放置在?n×n?的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数?n?，返回所有不同的?n?皇后问题?的解决方案。

每一种解法包含一个不同的?n 皇后问题?的棋子放置方案，该方案中?'Q'?和?'.'?分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

?

• 1 <= n <= 9

mp < rowSize && jTmp >= 0) {

? ? ? ? ? ? if (iTmp == mTarget && jTmp == nTarget) {

? ? ? ? ? ? ? ? return false;

? ? ? ? ? ? }

? ? ? ? ? ? iTmp++;

? ? ? ? ? ? jTmp--;

? ? ? ? }

? ? ? ? //-1,+1

? ? ? ? iTmp = isrc - 1;

? ? ? ? jTmp = jsrc + 1;

? ? ? ? while (iTmp >= 0 && jTmp < colSize) {

? ? ? ? ? ? if (iTmp == mTarget && jTmp == nTarget) {

? ? ? ? ? ? ? ? return false;

? ? ? ? ? ? }

? ? ? ? ? ? iTmp--;

? ? ? ? ? ? jTmp++;

? ? ? ? }

? ? ? ? //-1,-1

? ? ? ? iTmp = isrc - 1;

? ? ? ? jTmp = jsrc - 1;

? ? ? ? while (iTmp >= 0 && jTmp >= 0) {

? ? ? ? ? ? if (iTmp == mTarget && jTmp == nTarget) {

? ? ? ? ? ? ? ? return false;

? ? ? ? ? ? }

? ? ? ? ? ? iTmp--;

? ? ? ? ? ? jTmp--;

? ? ? ? }

? ? ? ? return true;

? ? }

? ? bool isCheck(vector<vector<bool>>& visited, int row, int col) {

? ? ? ? for (int i = 0; i < visited.size(); i++) {

? ? ? ? ? ? for (int j = 0; j < visited[0].size(); j++) {

? ? ? ? ? ? ? ? if (false == visited[i][j]) {

? ? ? ? ? ? ? ? ? ? continue;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if (i == row || j == col) {

? ? ? ? ? ? ? ? ? ? return false;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if (isVisited(visited.size(), visited[0].size(), i, j, row,

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? col) == false) {

? ? ? ? ? ? ? ? ? ? return false;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return true;

? ? }

? ? void backTrack(int n, int row, vector<vector<bool>>& visited) {

? ? ? ? if (row >= n) {

? ? ? ? ? ? vector<string> vec;

? ? ? ? ? ? for (int i = 0; i < n; i++) {

? ? ? ? ? ? ? ? string str = "";

? ? ? ? ? ? ? ? for (int j = 0; j < n; j++) {

? ? ? ? ? ? ? ? ? ? if (visited[i][j] == true) {

? ? ? ? ? ? ? ? ? ? ? ? str += "Q";

? ? ? ? ? ? ? ? ? ? } else {

? ? ? ? ? ? ? ? ? ? ? ? str += ".";

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? vec.push_back(str);

? ? ? ? ? ? }

? ? ? ? ? ? ret.push_back(vec);

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? for (int i = 0; i < n; i++) {

? ? ? ? ? ? if (visited[row][i] == true) {

? ? ? ? ? ? ? ? continue;

? ? ? ? ? ? }

? ? ? ? ? ? if (isCheck(visited, row, i) == false) {

? ? ? ? ? ? ? ? continue;

? ? ? ? ? ? }

? ? ? ? ? ? visited[row][i] = true;

? ? ? ? ? ? backTrack(n, row + 1, visited);

? ? ? ? ? ? visited[row][i] = false;

? ? ? ? }

? ? }

? ? vector<vector<string>> solveNQueens(int n) {

? ? ? ? vector<vector<bool>> visited(n, vector<bool>(n, false));

? ? ? ? backTrack(n, 0, visited);

? ? ? ? return ret;

? ? }

?