LeetCode 52 N皇后II

川长思鸟来 2022-05-12 05:18 164阅读 0赞

**LeetCod 52**

N皇后II

--------------------

首先，先看一下题目：  
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。  
![Image 1][]  
![这里写图片描述][70]  
上图为 8 皇后问题的一种解法。

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。  
\* 输入: 4  
输出: \[  
\[“.Q..”, // 解法 1  
“…Q”,  
“Q…”,  
“..Q.”\],

\[“..Q.”, // 解法 2  
“Q…”,  
“…Q”,  
“.Q..”\]  
\]

解释: 4 皇后问题存在两个不同的解法。

> 思路1：
> 
> Step1    放置棋子  
> \* 由于棋子不能放在同一行，所以按行放置
> 
> Step2    判断棋子是否合法  
> \* 判断当前列是否有棋子，所在对角线是否有棋子  
> ![Image 1][]  
> ![这里写图片描述][70 1]  
> Step3    循环上面两步，并且判断棋子是否放完，每放完一次下次先要判断是否放完  
> \* 判断要放的行是否走出了棋盘

class Solution {
    public:
        int totalNQueens(int n) {
            vector<int> pol(n,-1);
            dfsNQ(pol,0); 
            return count;
        }
        int count=0;
        void dfsNQ(vector<int> pol,int row){
            int n=pol.size();
            if(row==n){
                count++;
            }else{
                for(int i=0;i<n;i++)
                {
                    if(isPlace(pol,row,i))
                    {
                        pol[row]=i;
                        dfsNQ(pol,row+1);
                    }
                }
            }   
        }
        bool isPlace(vector<int> pol,int row,int col)
        {
            for(int i=0;i<row;i++)
            {
                if(pol[i]==col||abs(row-i)==abs(col-pol[i]))
                return false;
            }
            return true;
        }
    };

动动您可爱小手关注我：  
![Image 1][]  
![这里写图片描述][70 2]

[Image 1]: 
[70]: /images/20220512/3db3f6afedb141ab9b3d031183d46b6a.png
[70 1]: /images/20220512/eb7c6de5b0d7479d9f100e431ba98465.png
[70 2]: /images/20220512/2a5676707eb746bfa23a011bbbefe311.png