力扣第51题,N皇后,BFS+回溯

51. N皇后

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

上图为 8 皇后问题的一种解法。

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

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

示例:

输入: 4 输出: [ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],

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

思路和N皇后II一模一样,只是需要用string类型表示这一行的结果 直接看代码

#include<iostream>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

class Solution {
          
   
public:
	vector<vector<string>> res;
	int N;
	vector<vector<string>> solveNQueens(int n) {
          
   
		vector<bool> visited(n, false);  //某一列是否被使用
		N = n;
		vector<string> path;
		vector<int> col;   //下标是行,值是列
		dfs(0, visited,path,col);
		return res;
	}
	void dfs(int n, vector<bool>& visited, vector<string> &path,vector<int> &col)
	{
          
   
		if (n == N)
		{
          
   
			res.push_back(vector<string>(path));
			return;
		}
		for (int i = 0; i < N; i++)
		{
          
   
			if (!visited[i]){
          
   
				bool flag = true;
				for (int k = 0; k < n; k++)
				{
          
   //已经是不同行和不同列了,只需要和前面已经选好的行判断是否在一条对角线上即可
					if (abs(i - col[k]) == n - k){
          
   
						flag = false;
						break;
					}
				}
				if (flag)  //如果可以
				{
          
   
					col.push_back(i);
					string row(N, .);
					row[i] = Q;
					visited[i] = true;
					path.push_back(row);
					dfs(n + 1, visited, path, col);  //继续递归
					path.pop_back();  //撤销
					col.pop_back();
					visited[i] = false;
				}
			}
		}
	}
};

int main()
{
          
   
	Solution s;
	vector<vector<string>> a=s.solveNQueens(5);
	for (int i = 0; i < a.size(); i++)
	{
          
   
		for (int j = 0; j < a[0].size(); j++)
		{
          
   
			cout << a[i][j] << endl;
		}
		cout << endl;
	}
}