leetcode51. N皇后

  递归，一行一行放置，判断是否放置完成，完成则输出到result中。

　　

// Study.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <string>
#include <algorithm>
#include <sstream>
#include <set>
#include <stack>
#include <iomanip>
#define INT_MAX 2147483647 // maximum (signed) int value
#define INT_MIN (-2147483647 - 1) // minimum (signed) int value
;


using namespace std;

int Max(int a, int b)
{
	return a > b ? a : b;
}

int Min(int a, int b)
{
	return a < b ? a : b;
}

vector<vector<string>> result;
//将与 当前位置i,j 在一条直线的 found 设置为 .  后面的这些位置不可放置
void places_off(vector<vector<char>> &found, int i, int j)
{
	int n = found.size();
	if (i < 0 || j < 0 || i >= n || j >= n)
		return;

	//水平方向
	for (int k = 0; k < n; k++)
		found[i][k] = '.';
	//垂直方向
	for (int k = 0; k < n; k++)
		found[k][j] = '.';
	//对角线 右下方向：
	int k = 1;
	while (i + k < n && j + k < n)
	{
		found[i + k][j + k] = '.';
		k++;
	}
	//对角线 左下方向
	k = 1;
	while (i + k < n && j - k >= 0)
	{
		found[i + k][j - k] = '.';
		k++;
	}

	found[i][j] = 'Q';
}
void find_solution(vector<vector<char>> found,int n, int index)
{
	if (index >= n)
	{
		vector<string> rResult;
		string tmp;
		//将结果转换为指定输出格式
		for (auto vc : found)
		{
			tmp = "";
			for (auto c : vc)
				tmp += c;
			rResult.push_back(tmp);
		}
		result.push_back(rResult);
		return;
	}
	vector<vector<char>> tf;
	for (int j = 0; j < n; j++)
	{
		tf = found;
		//判断是否可以放置，可放置继续递归，否则进行下一次递归
		if (tf[index][j] == '0')
		{
			tf[index][j] = 'Q';
			places_off(tf, index, j);
			find_solution(tf, n, index + 1);
		}
	}
}
vector<vector<string>> solveNQueens(int n) {
	if (n < 1)
		return vector<vector<string>>();

	vector<vector<char>> found(n,vector<char>(n,'0'));

	find_solution(found ,n, 0);

	return result;
}
int main()
{
	vector<vector<string>> r;
	int n;
	while (1)
	{
		cin >> n;
		r = solveNQueens(n);
		for (auto g : r)
		{
			for (auto s : g)
				cout << s << " ";
			cout << endl;
		}
	}
	system("pause");
	return 0;
}