LeetCode51 N皇后

拼搏现实的明天。 2022-05-12 05:16 155阅读 0赞

**LeetCod 51**

N皇后

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

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

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

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

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

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

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

class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<string>> res;//返回结果
            vector<int> pla(n,-1);//第pla[i]表示第i行皇后的位置
            placeNQ(n,0,pla,res);//需要放n个棋子，从0（表示第一行）开始放
            return res;
        }
        void placeNQ(int n,int row,vector<int> pla,vector<vector<string>>& res)
        {
            if(row==n)//是否走出棋盘外
            {
                vector<string> out(n,string(n,'.'));
                for(int i=0;i<n;i++)
                {
                    out[i][pla[i]]='Q';//放置棋盘
                }
                res.push_back(out);
            }
            else{
    
            for(int col=0;col<n;col++)
            {
                if(isValid(row,col,pla))  //是否有效
                {
                    pla[row]=col;
                    placeNQ(n,row+1,pla,res); //继续下一行
                    //pla[row]=-1; 可写可不写
                }
            }
            }       
        }
      //判断棋子是否有效
        bool isValid(int row,int col,vector<int>& pla)   
        {
            for(int i=0;i<row;i++)
            {
                if(col==pla[i]||abs(row - i) == abs(col - pla[i]))
                    return false;
            }
            return true;
        }   
    };

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

[70]: /images/20220512/dbf1e42518924f8fb3a79011bd006f2e.png
[70 1]: /images/20220512/756c12836ab54c17abb179abae5a3e7b.png
[70 2]: /images/20220512/739b0f6f567e4751a41a927faecad6b0.png