LeetCode 51 N 皇后 - 回溯解法

https://leetcode.cn/problems/n-queens/description/

思路

for(0- n-1){
	if(i 位置合法，可以放皇后){
		path push
		add_path()
		path pop
	}
}

终止条件

if( path.size()==n)

判断合法

要求：同一行同一列只能有一个皇后，斜线也只能有一个。

分析：显然本行的皇后的位置受制于 path中已经加入的即：前面已经放置的皇后。

当前位置的受影响的位置为：loc[i]-(path.size()-i) 和 loc[i]+(path.size()-i)


合法为1，不合法为-1
vector<int> get_valid_loc(int n){
	vector<int> res;
	for(inti <size()){
		//同一列
		res[loc[i]] = -1;
		int left = loc[i]-(path.size()-i)
		int right = loc[i]+(path.size()-i)
		if(left>=0)  res[left] =-1;
		if(right<n)  res[right]  =-1;

	}
	return res;
}

代码

class Solution {

public:

    struct Path_node{

        vector<string> path;

        vector<int> q_loc;

    };

    Path_node path_node;

    vector<vector<string>> result;

    vector<int> get_val_loc(int n){

        vector<int> res(n,1);

        for(int i = 0;i<path_node.path.size();i++){

            res[path_node.q_loc[i]] = -1;

            int left = path_node.q_loc[i]-(path_node.path.size()-i);

            int right = path_node.q_loc[i]+(path_node.path.size()-i);

            if(left>=0){

                res[left] = -1;

            }

            if(right<n){

                res[right] = -1;

            }

        }

        return res;

    }

    void add_path(int n){

        if(path_node.path.size()==n){

            result.push_back(path_node.path);

            return;

        }

        vector<int> valid_loc = get_val_loc(n);

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

            if(valid_loc[i]==1){

                string tmp(n,'.');

                tmp[i] = 'Q';

                path_node.path.push_back(tmp);

                path_node.q_loc.push_back(i);

                add_path(n);

                path_node.path.pop_back();

                path_node.q_loc.pop_back();

            }

        }

    }

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

        add_path(n);

        return result;

    }

};