当前位置:网站首页>ACM解题笔记——HDU 1401 Solitaire(DBFS)
ACM解题笔记——HDU 1401 Solitaire(DBFS)
2022-08-10 20:51:00 【Dhaa_Ryan】
淦宁佬,能拿到蓝桥杯省二就算成功:(,ACM拿锤子奖,我这说唱专业的说唱学生百分百白给,是这样的
这只是我个人的备忘录 ,如果你能看得懂就将就看:P
玛德,刚开始写八字码问题把我给写麻了,然后晕乎乎的套八字码来解决这个问题,结果写了一晚上没写出来
今天用了DBFS,依旧把我写麻了,但是至少解出来了草
借鉴了下别人的思路,但是我依旧不知道为什么要给点排序,
不过没排序好像也给过,更奇怪的是,效率好像更高了,麻了
我猜如果用蛤希判重的话效率可能会更好一点,但是麻了的我已经不想写了
比赛遇到这种直接跳过吧(无慈悲)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include <string.h>
using namespace std;
char visit[8][8][8][8][8][8][8][8];
int dir[4][2] = {
{
-1,0 },{
1,0 },{
0,-1 },{
0,1 } };
struct point {
int x, y;
};
struct node {
struct point p[4]; //一种状态,四个棋子
int step;
};
node start, endr,ss;
//排序
int cmp(const point& p, const point& q) {
if (p.x == q.x)
return p.y < q.y;
return p.x < q.x;
}
int judge(node& s, int i, int j, int flag) {
//部属判断
if (flag == 1) {
if (s.step >= 4)//最多移动4步
return 0;
s.step++;
}
s.p[i].x += dir[j][0];
s.p[i].y += dir[j][1];
//判边界范围
if (s.p[i].x >= 0 && s.p[i].x < 8 && s.p[i].y >= 0 && s.p[i].y < 8) {
int k;
//判断点之间是否能一步跨入
for (k = 0; k < 4; k++) {
if (i != k) {
//判断是否有点,有点的话,递归判断下一个点
if (s.p[i].x == s.p[k].x && s.p[i].y == s.p[k].y)
if (flag == 1) return judge(s, i, j, 0);
else return 0;
}
}
//可以走
if (k >= 4) {
sort(s.p, s.p + 4, cmp);
return 1;
}
}
return 0;
}
int bfs() {
queue<node>Q1, Q2;
//初始化
Q1.push(start), Q2.push(endr);
visit[start.p[0].x][start.p[0].y][start.p[1].x][start.p[1].y][start.p[2].x][start.p[2].y][start.p[3].x][start.p[3].y] = '1';
visit[endr.p[0].x][endr.p[0].y][endr.p[1].x][endr.p[1].y][endr.p[2].x][endr.p[2].y][endr.p[3].x][endr.p[3].y] = '2';
while ((!Q1.empty()) || (!Q2.empty())) {
if (!Q1.empty()) {
for (int i = 0; i < 4; i++) {
//第i个棋子,搜的方向//这是搜走一步的
for (int j = 0; j < 4; j++) {
ss = Q1.front();
if (judge(ss, i, j, 1)) {
if (visit[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y] == '1')
continue;
//在Q2中已经搜过
if (visit[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y] == '2') {
return 1;
}
Q1.push(ss);
visit[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y] = '1';//在Q1中搜过的标记为'1';
}
}
}
Q1.pop();//出队列的时候一定要4颗棋子4个方向都试过才能出
}
if (!Q2.empty()) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
ss = Q2.front();
if (judge(ss, i, j, 1)) {
if (visit[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y] == '2')
continue;
//在Q1中已经搜过
if (visit[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y] == '1') {
return 1;
}
Q2.push(ss);
visit[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y] = '2'; //在Q2中搜过的标记为'2';
}
}
}
Q2.pop();
}
}
return 0;
}
int main() {
while (cin >> start.p[0].x >> start.p[0].y) {
//导入点,坐标要减一(减不减都行,但是大小得开够)
start.p[0].x--; start.p[0].y--;
for (int i = 1; i < 4; i++) {
cin >> start.p[i].x >> start.p[i].y;
start.p[i].x--; start.p[i].y--;
}
for (int i = 0; i < 4; i++) {
cin >> endr.p[i].x >> endr.p[i].y;
endr.p[i].x--; endr.p[i].y--;
}
start.step = endr.step = 0;
//搜之前先对棋子进行排序
sort(start.p, start.p + 4, cmp);
sort(endr.p, endr.p + 4, cmp);
memset(visit, 0, sizeof visit);
//搜!搜就完事了
if (bfs()) {
cout << "YES" << endl;
}else {
cout << "NO" << endl;
}
}
}
边栏推荐
猜你喜欢
win7开机有画面进系统黑屏怎么办
【语义分割】2016-SegNet TPAMI
apr_thread使用内存之谜
大小端的理解以及宏定义实现的理解
【语义分割】2015-UNet MICCAI
详叙c中的分支与循环
(十二)STM32——NVIC中断优先级管理
- [email protected] nanomimetic e"/>
Water-soluble alloy quantum dot nanozymes|CuMoS nanozymes|porous silicon-based Pt(Au) nanozymes|[email protected] nanomimetic e
壁仞推出全球最大算力芯片,号称以7nm超越英伟达4nm最新GPU
C语言系列——猜名次、猜凶手、打印杨辉三角
随机推荐
PostgreSQL — 安装及常用命令
npm‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件
第14届全国大学生信息安全竞赛-创新实践能力赛
这些mysql基础命令、基础知识还记得吗?(面试,学习,复习都可以)一万三千字总结
[SemiDrive source code analysis] [MailBox inter-core communication] 51 - DCF_IPCC_Property implementation principle analysis and code combat
饿了么-机构树单选
C. Social Distance
优化是一种习惯●出发点是'站在靠近临界'的地方
APP application related instructions in Auto.js
工程师应该怎么学习
第四届红帽杯网络安全大赛
2021 CybricsCTF
C语言系列——猜名次、猜凶手、打印杨辉三角
Transferrin (TF) Modified Paclitaxel (PTX) Liposomes (TF-PTX-LP) | Transferrin (Tf) Modified Curcumin Liposomes
MySQL查询数据库中的表和字段
大小端的理解以及宏定义实现的理解
金鱼哥RHCA回忆录:CL210OpenStack操作的故障排除--章节实验
论文解读(g-U-Nets)《Graph U-Nets》
设备管理中数据聚类处理
CGO 初步认知和基本数据类型转换