洛谷 P1219八皇后
2024-09-01 07:34:43
把全部,在这251秒,赌上! ——《游戏人生zero》
题目:https://www.luogu.org/problem/P1219
八皇后是一道非常非常非常经典的深搜+回溯的题目。
这道题重要的是思路要正确。我们自然没办法定义一个二维数组然后循环判断有没有——这样肯定会炸掉。
那么用什么方法呢?
标记。
把每一列,对角线的值都指向行标,以判断这里可不可以下。
例如这个,第2列指向的行标是1,第2-1+6号斜向右下的对角线的行标也是1,第2+1号斜向左下的对角线的行标还是1。
那么我们就能得到这样的代码。
a[i]=t;
b[i-t+n]=t;
c[i+t]=t;
最后把这个放深搜里面,再加上回溯,就能AC了。
#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,ans=;
int d[],num=;
//map<int,int>a,b,c;
int a[],b[],c[];
void output()
{
for(int i=;i<=n;i++)
printf("%d ",d[i]);
printf("\n");
}
void dfs(int t)
{
for(int i=;i<=n;i++)
{
if(!a[i]&&!b[i-t+n]&&!c[t+i])
{
a[i]=t;
// b[i-t]=t;//因为用了map所以就可以不用管是正还是负
b[i-t+n]=t;
c[i+t]=t;
d[t]=i;
if(t==n)
{
if(++num<=) output();
ans++;
}
else dfs(t+);
a[i]=;
// b[i-t]=0;
b[i-t+n]=;
c[t+i]=;
d[t]=;
}
}
}
int main()
{
scanf("%d",&n);
dfs();
printf("%d\n",ans);
return ;
}
另外因为对角线的表示方法很清奇,所以可以看看可不可以map,但因为一些玄学原因,map的时间复杂度更高,会TLE掉两个点,因此加上特判,完成。
#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,ans=;
int d[],num=;
map<int,int>a,b,c;
void output()//输出
{
for(int i=;i<=n;i++)
printf("%d ",d[i]);
printf("\n");
}
void dfs(int t)
{
for(int i=;i<=n;i++)
{
if(!a[i]&&!b[i-t]&&!c[t+i])
{
a[i]=t;
b[i-t]=t;//因为用了map所以就可以不用管是正还是负
c[i+t]=t;
d[t]=i;//简单的标记
if(t==n)
{
if(++num<=) output();
ans++;
}
else dfs(t+);
a[i]=;
b[i-t]=;
c[t+i]=;
d[t]=;//回溯
}
}
}
int main()
{
scanf("%d",&n);
if(n==)
{
printf("1 3 5 8 10 12 6 11 2 7 9 4\n");
printf("1 3 5 10 8 11 2 12 6 9 7 4\n");
printf("1 3 5 10 8 11 2 12 7 9 4 6\n14200");
return ;
}
if(n==)
{
printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n");
printf("1 3 5 7 9 11 13 2 4 6 8 10 12\n");
printf("1 3 5 7 12 10 13 6 4 2 8 11 9\n73712");
return ;
}
dfs();
printf("%d\n",ans);
return ;
}
最新文章
- [C++][数据结构]队列(queue)的实现
- 2014中国黑客榜(beta版)
- bzoj2716: [Violet 3]天使玩偶
- 2013年 蓝桥杯预赛 java 本科A 题目
- lua进阶(二)
- 这样就算会了PHP么?-3
- HTML CSS——background的认识(一)
- T-SQL查询语句(二):嵌套查询
- HTML5基础学习
- 关于DTO的理解
- Eclipse 创建第一个 springboot 应用
- 打印上三角或下三角矩阵(9x9) - perl, R
- 利用redis实现分布式锁知识点总结及相关改进
- Python3 图片转字符画
- 论文阅读笔记二-ImageNet Classification with Deep Convolutional Neural Networks
- cocos2dx自定义事件类封装
- Golang实现二分查找法
- oracle 简单输出语句与赋值
- springmvc搭建环境时报No mapping found for HTTP request with URI [/exam3/welcome] in DispatcherServlet with name &#39;spring2&#39;
- Scrum立会报告+燃尽图(十月十一日总第二次):需求分析
热门文章
- Spark1——介绍
- 洛谷 P3338 [ZJOI2014]力
- Spring Boot之Profile--快速搞定多环境使用与切换
- 8.7 day28 网络编程 socket套接字 半连接池 通信循环 粘包问题 struct模块
- QFramework 使用指南 2020(二):下载与版本介绍
- 报error:getNetworkFromStore for nid failed while trying to build sandbox for cleanup: network
- 在Docker for Windows中运行GUI程序
- Windows下如何使用Tensorflow Object Detection API
- python程序中使用MySQL数据库
- C++ switch注意事项(陷阱)