[洛谷/题目] P1562 还是N皇后

声明

关于科学道理都会放进代码中,但是我们需要先了解一下位运算解这道题目的基础知识

我不是很会专业词语,所以仅介绍原理

位运算基础

众所周知,二进制是0和1

2^3	2^2	2^1	2^0
8	4	2	1
0	1	0	1

对应的,加出来就是5,这就是二进制转换,我利用二进制里的0和1来记录是否走过或者其他的yes/no的数据,和bool数组一样

和bool数组相比,二进制虽然位数有限,但是非常方便,很多事情不需要人为的去干.

比如将bool数组的false的部分找出来,合并两个数组之类的.非常浪费精力

怎么单独更改一位呢?

这里有一个例子:

代码里有一个lowbit函数

这是怎么获取最后一个为1的那一位所表示的的数值呢?

这里有一个例子,具体是关于反码与补码的:

9:  1001

-9: 0111

9&(-9) = 1

1:  0001

"理论存在,实践开始"

#include <iostream>

using namespace std;

// n:棋盘格数 ans:答案个数 all:全部位数为1的二进制,是一个工具变量

int n, ans, all;

// row:每一行默认的棋盘 (全局默认清空,但是赋值更保险(好习惯)

int row[20] = {};

// 返回最后一个为1的那一位所表示的的数值

int lowbit(int x) {

	return x & (-x);

}

// d:当前第几行,从0开始 col:存储列是否用过 lv:存储左对角线是否用过 rv:存储右对角线是否用过

void dfs(int d, int col, int lv, int rv){

	if(d == n) {

		// 能走到最后一步就记录次数

		ans++;

		return ;

	}

	// 用位运算来获取遍历的依据 别忘了row是从1开始的

	int vis = all & (~(row[d + 1] | col | lv | rv));

	// 简单遍历

	for(int i = vis; i; i -= lowbit(i)) {

		int x = lowbit(i);

		// 下一步 为了适应行数的+1,对角线就要对应的左移或者右移

		dfs(d + 1, col + x, (lv + x) >> 1, (rv + x) << 1);

	}

}

int main(){

	// 零时变量,获取字符用

	char t;

	// 获取棋盘行列个数

	cin >> n;

	// 初始化为所有位数为1

	all = (1 << n) - 1;

	// 二位获取棋盘

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

		for(int j = 1; j <= n; j++){

			cin >> t;

			// 点为不能走(禁区)

			if(t == '.') {

				// 单独一行一列对应一个字节,更改即可

				// 加等于也是没有问题的

				row[i] |= (1<<(n - j));

			}

		}

	}

	// 开始深搜 0的所有位都为0

	dfs(0, 0, 0, 0);

	// 换行好习惯

	cout << ans << endl;

	return 0;

}

总结

题目很好,可以锻炼思维,突破传统的思维方式,打开一个新世界的大门

好久没有写过markdown,生疏了

哦吼吼,能看到这个链接就说明我的文章被爬虫爬了

请尊重原作者: https://www.cnblogs.com/dffxd/

小学四五年级可以学习到s组就是一个畸形的教育体系的体现,等国家发展起来了,吃枣药丸

巴特西

[洛谷/题目] P1562 还是N皇后

声明

位运算基础

总结

最新文章

热门文章