N 皇后(原始方法)

待我称王封你为后i 2022-12-07 15:15 106阅读 0赞

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

![format_png][]

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

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

示例:

输入: 4  
输出: 2  
解释: 4 皇后问题存在如下两个不同的解法。  
\[  
\[".Q..", // 解法 1  
"...Q",  
"Q...",  
"..Q."\],

\["..Q.", // 解法 2  
"Q...",  
"...Q",  
".Q.."\]  
\]

解法:

原始方法直接遍历棋盘,把每个棋盘的每种情况都尝试一遍,不推荐使用

const int N = 1010;
    class Solution {
    public:
        char grid[N][N];  
        bool row[N],col[N],dg[N],udg[N];
        int un,res = 0;
        void qdfs(int x,int y,int s){   //s表示要不要摆
            if(y == un){ //横着走到边界
                y = 0,x++;
            }
            if(x == un){  //走到棋盘中的最后一格
                if(s == un){
                    res++;
                }
                return;
            }
            qdfs(x,y+1,s);  //决策1不摆
            //决策2 摆
            if(!row[x] && !col[y] && !dg[x+y] && !udg[un-y+x]){
                row[x] = col[y] = dg[x+y] = udg[un-y+x] = true;
                grid[x][y] = 'Q';
                qdfs(x,y+1,s+1);
                row[x] = col[y] = dg[x+y] = udg[un-y+x] = false;
                grid[x][y] = '.';
            }
        }
        int totalNQueens(int n) {
            un = n;
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < n; ++j){
                    grid[i][j] = '.';
                }
            }
            qdfs(0,0,0);
            int sres = res;
            return sres;
        }
    };

[format_png]: /images/20221123/f2671e92ac2a4770aed93941007f0422.png

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 51N皇后 52N皇后II

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有不同的 n 皇

朱雀/ 2023年06月19日 09:43/ 0 赞/ 193 阅读

相关 N 皇后(原始方法)

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 ![format_png][] 上图为 8 皇后问题的一种解法。给定一

待我称王封你为后i/ 2022年12月07日 15:15/ 0 赞/ 107 阅读

相关 N 皇后！

提到回溯算法那肯定离不开 n 皇后这道算法题，它实在是太经典了。所谓 n 皇后问题，指的是如何将 `n` 个皇后放置在 `n×n` 的棋盘上，并且使皇后彼此之间不能相互攻

快来打我*/ 2022年09月12日 07:51/ 0 赞/ 272 阅读

相关 n皇后问题

目前会的一种解决n皇后的方法，在笔记本上大概能解除10以内的问题，更大规模的还要再去学习其他的人的好方法 include<iostream> usi

曾经终败给现在/ 2022年08月20日 06:24/ 0 赞/ 191 阅读

相关 n皇后问题

n皇后问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述在n×n 格的棋盘上放置

小鱼儿/ 2022年08月18日 02:30/ 0 赞/ 181 阅读

相关二N皇后

package 搜索; import java.io.BufferedReader; import java.io.IOException;

妖狐艹你老母/ 2022年07月12日 12:13/ 0 赞/ 131 阅读

相关 [Leetcode][python]N-Queens/N-Queens II/N皇后/N皇后 II

N-Queens 题目大意经典的八皇后问题的一般情况注意点：皇后用”Q”表示，空白用”.”表示解题思路回溯法，位运算等，见总结代码

﹏ヽ暗。殇╰゛Y/ 2022年06月07日 04:47/ 0 赞/ 196 阅读

相关 N 皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包

喜欢ヅ旅行/ 2022年05月17日 04:52/ 0 赞/ 217 阅读

相关 LeetCode：N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 ![在这里插入图片描述][20190804135824382.png]

朴灿烈づ我的快乐病毒、/ 2021年11月11日 05:28/ 0 赞/ 287 阅读

相关 51. N皇后

51. N皇后题目描述 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 ![8-queens.png][]

绝地灬酷狼/ 2021年11月02日 00:08/ 0 赞/ 317 阅读