P1562 还是N皇后
admin
2024-03-16 10:20:26
0次
知识点：深搜，剪枝，位运算
难度：3
感觉这个题还是比别的难度为3的题要难一些，因为用到了状压搜索，我这里使用的写法是把每一行的状态当成了函数参数的写法，也就是函数里面有三个参数表示状态，每个数表示当前行的每一列当前情况下是不是可选的点，第一个是竖直，第二个是右上到左下的对角线，第三个是左上到右下的对角线，然后我们向下一层递归的时候要计算出新的参数，两个对角线分别需要用到移位运算，然后高位低位分别补1，
我这个时间效率还不是很高，1.8s，我看洛谷其它的提交基本上都是1s左右，甚至还有500ms的，说明我这个还有将近一倍的优化空间，而且我这个不能放置的点是在递归函数里面判断的，不是一开始就预处理好的
#include using namespace std;const int N = 14;int n, ans, h[1 << N];
string s[N];int lowbit(int x) {return x & -x;
}void dfs(int k, int col, int dia1, int dia2) {if (k == n) {ans++;return;}int num = col & dia1 & dia2;for (int i = num; i; i -= lowbit(i)) {int t = lowbit(i);if (s[k][h[t]] == '.') continue;col -= t;int t1 = dia1, t2 = dia2;dia1 = ((dia1 - t) >> 1) + (1 << (n - 1));dia2 = ((dia2 - t) << 1) + 1;dia2 &= (~(1 << n));dfs(k + 1, col, dia1, dia2);col += t;dia1 = t1; dia2 = t2;}
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> s[i];h[1 << i] = i;}int init = (1 << n) - 1;dfs(0, init, init, init);cout << ans;return 0;
} 相关内容
热门资讯
linux入门---制作进度条
了解缓冲区 我们首先来看看下面的操作： 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统（六）：学...
8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤： 在Student.cpp的...
A.机器学习入门算法（三）：基...
机器学习算法（三）：K近邻(k-nearest neigh...
数字温湿度传感器DHT11模块...
模块实例https://blog.csdn.net/qq_38393591/article/deta...
有限元三角形单元的等效节点力
文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数（Nÿ...
Redis 所有支持的数据结构...
Redis 是一种开源的基于键值对存储的 NoSQL 数据库，支持多种数据结构。以下是...
win下pytorch安装—c...
安装目录一、cuda安装1.1、cuda版本选择1.2、下载安装二、cudnn安装三、pytorch...
MySQL基础-多表查询
文章目录MySQL基础-多表查询一、案例及引入1、基础概念2、笛卡尔积的理解二、多表查询的分类1、等...
keil调试专题篇
调试的前提是需要连接调试器比如STLINK。 然后点击菜单或者快捷图标均可进入调试模式。 如果前面...
MATLAB | 全网最详细网...
一篇超超超长，超超超全面网络图绘制教程，本篇基本能讲清楚所有绘制要点&#...
IHome主页 - 让你的浏览...
随着互联网的发展，人们越来越离不开浏览器了。每天上班、学习、娱乐，浏览器...
TCP 协议
一、TCP 协议概念 TCP即传输控制协议（Transmission Control ...
营业执照的经营范围有哪些
营业执照的经营范围有哪些 经营范围是指企业可以从事的生产经营与服务项目，是进行公司注册...
C++ 可变体(variant...
一、可变体(variant) 基础用法 Union的问题： 无法知道当前使用的类型是什...
血压计语音芯片，电子医疗设备声...
语音电子血压计是带有语音提示功能的电子血压计，测量前至测量结果全程语音播报...
MySQL OCP888题解0...
文章目录1、原题1.1、英文原题1.2、答案2、题目解析2.1、题干解析2.2、选项解析3、知识点3...
【2023-Pytorch-检...
（肆十二想说的一些话）Yolo这个系列我们已经更新了大概一年的时间，现在基本的流程也走走通了，包含数...
实战项目：保险行业用户分类
这里写目录标题1、项目介绍1.1 行业背景1.2 数据介绍2、代码实现导入数据探索数据处理列标签名异...
记录--我在前端干工地(thr...
这里给大家分享我在网上总结出来的一些知识，希望对大家有所帮助 前段时间接触了Th...
43 openEuler搭建A...
文章目录43 openEuler搭建Apache服务器-配置文件说明和管理模块43.1 配置文件说明...