LeetCode52——N-Queens II

我就是我 2022-08-09 12:56 32阅读 0赞

LeetCode52——N-Queens II

跟[LeetCode51][]一样，只不过这题是求解解的个数。

这里我套用了上一题的代码，只不过当row==n（递归返回条件）时，不是将一种可行解加入结果集，而是另计数变量自增，来统计可行解的数量。

代码：

class Solution {
    private:
    	int num;
    	bool check(int row, int col, int n, vector<string>m)
    	{
    		if (row == 0)
    			return true;
    		int i;
    		int j;
    		for (i = 0; i < row; i++)
    		{
    			if (m[i][col] == 'Q')
    				return false;
    		}
    		i = row - 1;
    		j = col - 1;
    		while (i >= 0 && j >= 0)
    		{
    			if (m[i][j] == 'Q')
    				return false;
    			i--;
    			j--;
    		}
    		i = row - 1;
    		j = col + 1;
    		while (i >= 0 && j < n)
    		{
    			if (m[i][j] == 'Q')
    				return false;
    			i--;
    			j++;
    		}
    		return true;
    	}
    	void add(vector<string>m)
    	{
    		num++;
    	}
    	void solve(int row, int n, vector<string>m)
    	{
    		int col;
    		if (row == n)
    		{
    			add(m);
    			return;
    		}
    		for (col = 0; col<n; col++)
    		{
    			if (check(row, col, n, m) == true)
    			{
    				m[row][col] = 'Q';
    				solve(row + 1, n, m);
    				m[row][col] = '.';
    			}
    		}
    	}
    public:
    		int totalNQueens (int n) {
    		vector<string>m(n, string(n, '.'));
    		num = 0;
    		solve(0, n, m);
    		return num;
    	}
    };

[LeetCode51]: http://blog.csdn.net/zhangxiao93/article/details/49388141

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode52. N皇后 II 最强解法直接秒杀100%

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

短命女/ 2023年07月03日 02:47/ 0 赞/ 2 阅读

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

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

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

相关 LeetCode 52. N皇后 II JAVA

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

落日映苍穹つ/ 2022年12月15日 14:18/ 0 赞/ 141 阅读

相关 leetcode52.N皇后 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6

矫情吗；*/ 2022年09月08日 11:31/ 0 赞/ 153 阅读

相关 LeetCode52——N-Queens II

LeetCode52——N-Queens II 跟[LeetCode51][]一样，只不过这题是求解解的个数。这里我套用了上一题的代码，只不过当row==n（递归返回条件

我就是我/ 2022年08月09日 12:56/ 0 赞/ 33 阅读

相关 leetcode 52. N-Queens II DFS深度优先遍历

Follow up for N-Queens problem. Now, instead outputting board configurations, return th

蔚落/ 2022年06月09日 10:42/ 0 赞/ 136 阅读

相关 LeetCode 52 N皇后II

LeetCod 52 N皇后II -------------------- 首先，先看一下题目： n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘

川长思鸟来/ 2022年05月12日 05:18/ 0 赞/ 165 阅读

相关 52. N-Queens II

class Solution { public int totalNQueens(int n) { int[][] board=

以你之姓@/ 2021年12月22日 06:49/ 0 赞/ 219 阅读

相关 52.N-Queens II

Follow up for N-Queens problem. Now, instead outputting board configurations, return th

朴灿烈づ我的快乐病毒、/ 2021年10月29日 15:56/ 0 赞/ 286 阅读

相关 52.N皇后 II

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

素颜马尾好姑娘i/ 2021年06月10日 20:39/ 0 赞/ 400 阅读