一题多解-八数码(万字长文)
16
张炜皓 (ζ͡顾念̶°) LV 5 @ 1 周前
在做这道题前,先来认识一下deque双端队列
C++ STL 中的双端队列
题目连接
使用前需要先引入 头文件。 #include;
STL 中对 deque 的定义
// clang-format off
template<
class T,
class Allocator = std::allocator
class deque;
T 为 deque 中要存储的数据类型。
Allocator 为分配器,此处不做过多说明,一般保持默认即可。
STL 中的 deque 容器提供了一众成员函数以供调用。其中较为常用的有:
元素访问
q.front() 返回队首元素
q.back() 返回队尾元素
修改
q.push_back() 在队尾插入元素
q.pop_back() 弹出队尾元素
q.push_front() 在队首插入元素
q.pop_front() 弹出队首元素
q.insert() 在指定位置前插入元素(传入迭代器和元素)
q.erase() 删除指定位置的元素(传入迭代器)
容量
q.empty() 队列是否为空
q.size() 返回队列中元素的数量
此外,deque 还提供了一些运算符。其中较为常用的有:
使用赋值运算符 = 为 deque 赋值,类似 queue。
使用 [] 访问元素,类似 vector。
头文件中还提供了优先队列 std::priority_queue,因其与堆更为相似,在此不作过多介绍。
来上正解
点击展开代码
点击展开代码
点击展开代码
点击展开代码
点击展开代码
点击展开代码
点击展开代码啊!!!
点击上面啊!
点击上面啊!
点击上面啊!
友情链接
点击上面啊!
------------------------------
初一18班范梓彬 LV 4 @ 1 周前
```
#include
#include
#include
#include
using namespace std;
struct Map{
int x,y,arr[3][3],step;
Map(){
step=0;
}
}st,ed;
deque
李咏航 (20221020) LV 8 @ 2 个月前
排版有点乱,建议看(也是我写的)【BFS】八数码问题(c++基础算法)
一.读题
作为最经典的一道宽度优先搜索题,它的题面并不是很难懂。
【宽搜(难度:6)】8数码问题 题目描述 【题意】 在3×3的棋盘上摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围上下左右相邻的棋子可以移到空格中。 现给出原始状态和目标状态,求实现从初始布局到目标布局的最少步骤(初始状态的步数为0)。 如下图,答案为5。
【输入格式】 第一个33的矩阵是原始状态; 第二个33的矩阵是目标状态。 【输出格式】 输出移动所用最少的步数。
【样例1输入】 2 8 3 1 6 4 7 0 5 1 2 3 8 0 4 7 6 5
【样例1输出】 5
【样例2输入】 2 8 3 1 6 4 7 0 5 0 1 2 3 4 5 8 7 6
【样例2输出】 17
很显然,这是要我们求出矩阵1通过白色方块的上下左右移动转化向矩阵2的最小步数。
二.在做题之前
在做题之前,我们先要弄懂3个问题。
1.康拓展开
在这道题中,我们要利用康托展开判断是否重复。在文前,蒟蒻已经写了一篇文章,不懂的可以去看一下:【宽搜必备】康托展开(从公式解析到代码实现)
那么,我们就可以写出:
{
int s=1;
for(int i=1;i<=n;i++)
{
int index=1,f=1,count=0;
for(int j=i+1;j<=n;j++)
{
f*=index;
index++;
if(a[i]>a[j]) count++;
}
s=s+count*f;
}
return s;
}
2.DFS和BFS的区别
bfs 遍历节点是先进先出,dfs遍历节点是先进后出; bfs是按层次访问的,dfs 是按照一个路径一直访问到底,当前节点没有未访问的邻居节点时,然后回溯到上一个节点,不断的尝试,直到访问到目标节点或所有节点都已访问。 bfs 适用于求源点与目标节点距离最近的情况,例如:求最短路径。dfs 更适合于求解一个任意符合方案中的一个或者遍历所有情况,例如:全排列、拓扑排序、求到达某一点的任意一条路径。
3.栈和队列的区别
(1)栈和队列的出入方式不同:栈是后进先出、队列是先进先出。 (2)栈和队列在具体实现的时候操作的位置不同:因为栈是后进先出,它在一段进行操作;而队列是先进先出,实现的时候在两端进行。
现在,我们搞懂了这三个问题,就可以做题了。
三.做题
1.算法原理
采用BFS遍历的方式寻找最优路径。
首先定义一个结构体ma来存放八数码的每一个状态信息,其中包括节点对应的矩阵,节点在BFS遍历树中的深度(相当于步数),以及节点对应的康托值。然后,定义visited数组存放已经访问过的节点状态。
利用队列实现遍历,具体步骤如下:
1.将初始状态的各种信息压入队列中。 2.判断队列是否为空,若为空,退出循环,打印移动步骤,结束。 3.取出队头元素判断是否与目标状态一致。若一致,则退出循环,输出移动步骤,程序结束。若不一致,则分别判断空格向左、向上、向下以及向右能否移动。 5.若可以移动,求其康托值,然后压进队列。并跳转到步骤四。
2.算法实现
①队列
因为此队列要存的东西是一个结构体,因此也要把其类型定为结构体ma
②康托展开
在此代码中,康托展开用于判重。要将一个3*3的矩阵换为一个数。首先,我们要把此二维数组变为一维的。
int d[10],len = 0;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
d[++len] = ak.a[i][j];
}
}
然后,进行康拓转化。最后就是这样
int
{
int d[10],len = 0;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
d[++len] = ak.a[i][j];
}
}
int s=1;
for(int i=1;i<=9;i++)
{
int index=1,f=1,count=0;
for(int j=i+1;j<=9;j++)
{
f=findex,index++;
if(d[i]>d[j]) count++;
}
s=s+countf;
}
return s;
}
③标记
很简单,用数组flag标记康托值即可
四.AC代码
基本队列
好吧,黑历史。。。
#include<bits/stdc++.h>
using namespace std;
struct node{
int kt,a[10][10],bs,x,y;
}st,ed;
queueq;
bool bo[1000005];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int cantor(node ha)
{
int b[15],s=0;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
b[3*(i-1)+j]=ha.a[i][j];
}
}
for(int i=1;i<=9;i++)
{
int f=1,index=1,count=0;
for(int j=i+1;j<=9;j++)
{
if(b[i]>b[j]) count++;
f*=index;
index++;
}
s+=count*f;
}
return s;
}
int main()
{
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
scanf(“%d”,&st.a[i][j]);
if(st.a[i][j]==0)
{
st.x=i;
st.y=j;
}
}
}
st.kt=cantor(st);
st.bs=0;
bo[st.kt]=1;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
scanf(“%d”,&ed.a[i][j]);
}
}
ed.kt=cantor(ed);
q.push(st);
while(!q.empty())
{
for(int i=0;i<4;i++)
{
node ne=q.front();
ne.bs++;
ne.x+=dx[i],ne.y+=dy[i];
swap(ne.a[ne.x][ne.y],ne.a[q.front().x][q.front().y]);
ne.kt=cantor(ne);
if(ne.x>=1&&ne.x<=3&&ne.y>=1&&ne.y<=3&&bo[ne.kt]0)
{
q.push(ne);
bo[ne.kt]=1;
if(ne.kted.kt)
{
cout<<ne.bs;
return 0;
}
}
}
q.pop();
}
}
双端队列做法
既然老师教的是双端队列,那么我也更新一下。。。
C++ STL 中的双端队列
此部分转载自zhangweihao的“原创”
使用前需要先引入 头文件。 #include;
STL 中对 deque 的定义
// clang-format off
template<
class T,
class Allocator = std::allocator
class deque;
T 为 deque 中要存储的数据类型。
Allocator 为分配器,此处不做过多说明,一般保持默认即可。
STL 中的 deque 容器提供了一众成员函数以供调用。其中较为常用的有:
元素访问
q.front() 返回队首元素
q.back() 返回队尾元素
修改
q.push_back() 在队尾插入元素
q.pop_back() 弹出队尾元素
q.push_front() 在队首插入元素
q.pop_front() 弹出队首元素
q.insert() 在指定位置前插入元素(传入迭代器和元素)
q.erase() 删除指定位置的元素(传入迭代器)
容量
q.empty() 队列是否为空
q.size() 返回队列中元素的数量
此外,deque 还提供了一些运算符。其中较为常用的有:
使用赋值运算符 = 为 deque 赋值,类似 queue。
使用 [] 访问元素,类似 vector。
头文件中还提供了优先队列 std::priority_queue,因其与堆更为相似,在此不作过多介绍。
代码
#include<bits/stdc++.h>
using namespace std;
struct ma{
int a[10][10],x0,y0,ans,kt;
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
dequeq;
bool flag[4001000];
int kt(ma ak)
{
int d[10],len = 0;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
d[++len] = ak.a[i][j];
}
}
int s=1;
for(int i=1;i<=9;i++)
{
int index=1,f=1,count=0;
for(int j=i+1;j<=9;j++)
{
f=findex,index++;
if(d[i]>d[j]) count++;
}
s=s+countf;
}
return s;
}
int main()
{
ma shi,mo;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
scanf(“%d”,&shi.a[i][j]);
if(shi.a[i][j]0)
{
shi.x0=i,shi.y0=j;
}
}
}
shi.ans = 0;
shi.kt = kt(shi);
flag[shi.kt] = 1;
q.push_back(shi);
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
scanf(“%d”,&mo.a[i][j]);
}
}
mo.kt=kt(mo);
while(!q.empty())//q非空,可以走
{
for(int i=0;i<4;i++)//四个方向
{
ma ac=q.front();
int nx = ac.x0 + dx[i];
int ny = ac.y0+ dy[i];
if(nx>=1&&ny>=1&&nx<=3&&ny<=3)
{
swap(ac.a[ac.x0][ac.y0],ac.a[nx][ny]);
ac.x0=nx;
ac.y0=ny;
//将0与目标数交换
ac.ans++;//步数加1
ac.kt=kt(ac);
//康托判重
if(!flag[ac.kt])
{
flag[ac.kt] = 1;
q.push_back(ac);
//加入队列
if(ac.ktmo.kt)
{
printf(“%d”,q.back().ans);
exit(0);
}
}
}
}
q.pop_front();
//弹出已遍历完所有情况的矩阵
}
}
初一18班范梓彬 @ 1 周前
是真的六,是不是闲得慌
谢信宇 @ 1 周前
大神帮帮我解决那个问题呗`
#include
#include
#include
#include
using namespace std;
struct Map{
int x,y,arr[3][3],step;
Map(){
step=0;
}
}st,ed;
deque
5一中谭智轩 LV 6 @ 1 周前
#include
#include<cstring>
#include<algorithm>
using namespace std;
struct Map{
int x, y, step, arr[3][3];//arr是棋盘, x是行方位, y是列方位,step是步数。
Map(){
step=0; //步数为0;
}
}st, ed, list[370000];//起点,结束点, 队列;bool v[370000];
int front = 0,rear = -1;//首指针,尾指针
//向各面走
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};int Cantor(int a[], int len) {//算当前的排列在全排列中排第几个(康拓值)
int ans=0;
for(int i=0; i<len; i++) {
int count=0, index = 1, f=1;
for(int j=i+1; j<len; j++) {
if(a[i] > a[j]) //算当前未出现的数字中有几个比已知排列的第i位小
count++;
f*=index++;
}
ans+=count*f; //算阶乘
}
return ans;
}
int CantorMap(Map map) { //将二维棋盘化为一维(数列)
int b[9];
memset(b,0,sizeof(b));
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
b[i*3+j]=map.arr[i][j]; //因为是3*3的棋盘, so......
return Cantor(b,9); //算康托值, 像名字一样用
}int main(){
memset(v,0,sizeof(v));
//输入起始状态和最终状态
for(int i=0;i<3;i++)
for(int j=0;j<3;j++) {
int temp;
scanf("%d",&temp); //输入初始的状态
if(temp==0) {
st.x=i,st.y=j; //0(空格)的位置
}
st.arr[i][j]=temp;
}
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
scanf("%d",&ed.arr[i][j]); //输入目标状态
}
}
v[CantorMap(st)]=true; //将这个状态的康拓值命名为已用
list[++rear] = st; //入队
int tg = CantorMap(ed); //将结束值化为'名'
while(front<=rear) { //如果队列未清空
for(int i=0;i<4;i++) {
Map map = list[front];//将当前状态移到队首
//试方案
int xx = map.x+dx[i];
int yy = map.y+dy[i];
if(xx>=0 && xx<=2 && yy>=0 && yy<=2) {
//移动,也就是交换
swap(map.arr[map.x][map.y],map.arr[xx][yy]);
map.x=xx;
map.y=yy;
map.step++; //步数+1;
}
//如果已经走过了,就不走了
if(v[CantorMap(map)]) continue;
//如果当前状态等于目标状态,就输出步数
if(tg==CantorMap(map)) {
printf("%d",map.step);
return 0;
}
list[++rear] = map;//不然就再次移动(改变状态)
v[CantorMap(map)] = true; //已用
}
front++; //出队,换下种状态试。
}
return 0;
}宽搜的试方案顺序 (注意:每方案表示一个状态) 按此数字从小到大试1
2 3 4 5
6 7 8 9 10 11 1213 14151617 18192021
还有很多分杈(上图省略了)
本题中宽搜是一个四杈数 !!!
但因为这么多状态中有很多是重复的, so要用 bool v数组来避免走重复的状态
试完一个状态后, 如果他不是目标状态,将他出队, 并将他下面的四杈入队。然后继续是如图中同行的下一个状态
假设 ‘+ ’表试入队, ‘- ’表示出队, ‘e ’表示试一次方案, , '1e' 表示试一次方案一 , 那么上图的试状态顺序如下 (一直没试到方案的情况)
+1 1e -1 +2+3+4 2e +6+7+8+9 -2 3e +10+11+12+13 -3 e4 +14+15+16+17 -4 e5 +18+19+20+21 -5 e6......一中谭智轩 @ 1 周前
由于hydro的题解编辑实在是一言难尽,所以这题解有点......李咏航 (20221020) @ 1 周前
@ 一中谭智轩 是MarkDown一个 垃圾 很好的编译器啊!
3谢东阳 (20221243) LV 7 @ 1 周前
宽搜这东西,无非就是...1: O / \
2: O O/ \ / \
3: O O O O
....................
很多人都不理解一个东西(比如曾经的我) 那就是... 西天的东方不败:struct Map{int x,y,step,arr[3][3];Map() {step=0;}
}st,ed,list[440000];
list:对的,那个东方不败就是我。 虽然我们已经学了deque, 这个长得奇奇怪怪的东西...但
必须要理解宽搜的原理,这个list是什么? (list:*******) 已经知道了宽搜的遍历顺序了,但是怎么实现呢? 众所周知,dfs是通过函数里面写函数来进行单个遍历的,如果写在一个main函数里面,就是一堆while。 但是宽搜不一样啊,这遍历顺序可比dfs难表达。 这时候,list它他(list本人要求用单人旁的ta)登场了! 有list之前,宽搜是这样的!1: O / \
2: O O/ \ / \
3: O O O O
....................
我们还是标上序号吧!一: 1 / \
二: 2 5/ \ / \
三: 3 4 6 7
....................
我这里的序号,是用dfs的顺序写的。 好了,用dfs的遍历顺序,就是...1 2 3 4 5 6 7
那用bfs呢?就是这样的!list[1] list[2] list[3] ...
(list:*******) 搞错了,再来:1 2 5 3 4 6 7
OK啊,那么list,就是对应了每一个数字,每一个list,都是这个队列中的一个,酱紫,就可以解决顺序问题啦! (list此时正得意洋洋的看着你)但!
list已经成为了过去,现在,是deque的时代。 (deque: dide que shi de) (list:T-T)虽然用了deque,就不用list了,而且list的两个小弟front和rear也会离开。 但他们成为了deque的一员,在数字生命世界deque中活着... 好了,宽搜的大致原理讲完了,具体怎么做,就交给代码了。什么?你还要看代码? 21世纪了,还有人想看代码? 看别人去吧,这个世界不缺代码...(代码:qwq)点赞不点赞自己选,反正...(懂得都懂)谢东阳 (20221243) @ 1 周前
写的有点模糊,只是按自己的理解写了大概原理,似乎废话有点多...见谅。3初一18班范梓彬 LV 4 @ 1 周前
【宽搜(难度:6)】8数码问题 题目描述 【题意】 在3×3的棋盘上摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围上下左右相邻的棋子可以移到空格中。 现给出原始状态和目标状态,求实现从初始布局到目标布局的最少步骤(初始状态的步数为0)。 如下图,答案为5。【输入格式】 第一个33的矩阵是原始状态; 第二个33的矩阵是目标状态。 【输出格式】 输出移动所用最少的步数。【样例1输入】 2 8 3 1 6 4 7 0 5 1 2 3 8 0 4 7 6 5【样例1输出】 5【样例2输入】 2 8 3 1 6 4 7 0 5 0 1 2 3 4 5 8 7 6【样例2输出】 17#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Map{int x,y,arr[3][3],step;Map(){step=0;}
}st,ed,list[370000];
bool v[370000];
int front=0,rear=-1;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int Cantor(int a[],int len){int ans=0;for(int i=0;i<len;i++){int count=0,index=1,f=1;for(int j=i+1;j<len;j++){if(a[i]>a[j])count++;f*=index++;}ans+=count*f;}return ans;
}
int CantorMap(Map map){int b[9];memset(b,0,sizeof(b));for(int i=0;i<3;i++)for(int j=0;j<3;j++)b[i*3+j]=map.arr[i][j];return Cantor(b,9);
}
int main(){memset(v,false,sizeof(v));for(int i=0;i<3;i++)for(int j=0;j<3;j++){int temp;scanf("%d",&temp);if(temp==0){st.x=i,st.y=j;}st.arr[i][j]=temp;}for(int i=0;i<3;i++)for(int j=0;j<3;j++)scanf("%d",&ed.arr[i][j]);v[CantorMap(st)]=true;list[++rear]=st;int tg=CantorMap(ed);while(front<=rear){for(int i=0;i<4;i++){Map map=list[front];int xx=map.x+dx[i];int yy=map.y+dy[i];if(xx>=0&&xx<=2&&yy>=0&&yy<=2){swap(map.arr[map.x][map.y],map.arr[xx][yy]);map.x=xx;map.y=yy;map.step++;}if(v[CantorMap(map)]) continue;if(tg==CantorMap(map)){printf("%d",map.step);return 0;}list[++rear]=map;v[CantorMap(map)]=true;}front++;} return 0;
}
好评2谢信宇 LV 5 @ 1 周前
SOS
此蒟蒻问问各位大神如何不用康托的代码去实现deque双端队列 下面给出的代码是我的,但样例过了,递交的时候有两个是TLE和MLE,我相信你们的脑瓜子能用上述方法做出来的😄#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
struct Map{int x,y,arr[3][3],step;Map(){step=0;}
}st,ed;
deque<Map>dq;
bool v[370000];
int front=0,rear=-1;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int Cantor(int a[],int len){int ans=0;for(int i=0;i<len;i++){int count=0,index=1,f=1;for(int j=i+1;j<len;j++){if(a[i]>a[j])count++;f*=index++;}ans+=count*f;}return ans;
}
int CantorMap(Map map){int b[9];memset(b,0,sizeof(b));for(int i=0;i<3;i++)for(int j=0;j<3;j++)b[i*3+j]=map.arr[i][j];return Cantor(b,9);
}
int main(){memset(v,false,sizeof(v));for(int i=0;i<3;i++)for(int j=0;j<3;j++){int temp;scanf("%d",&temp);if(temp==0){st.x=i,st.y=j;} st.arr[i][j]=temp;}for(int i=0;i<3;i++)for(int j=0;j<3;j++)scanf("%d",&ed.arr[i][j]);v[CantorMap(st)]=true;//list[++rear]=st;dq.push_back(st);int tg=CantorMap(ed);while(!dq.empty()){for(int i=0;i<4;i++){Map map=dq.front();int xx=map.x+dx[i];int yy=map.y+dy[i];if(xx>=0&&yy>=0&&xx<=2&&yy<=2){swap(map.arr[map.x][map.y],map.arr[xx][yy]);map.x=xx;map.y=yy;map.step++;}if(v[CantorMap(map)])continue;if(tg==CantorMap(map)){printf("%d",map.step);return 0;}//list[++rear]=map;dq.push_back(map);v[CantorMap(map)]=true; }//front++;dq.pop_front();}return 0;
}李咏航 (20221020) @ 1 周前
就是不行,所以才有了cantor
2谢信宇 LV 5 @ 1 周前
SOS
此蒟蒻问问各位大神如何不用康托的代码去实现deque双端队列 下面给出的代码是我的,但样例过了,递交的时候有两个是TLE和MLE,我相信你们的脑瓜子能用上述方法做出来的😄#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
struct Map{int x,y,arr[3][3],step;Map(){step=0;}
}st,ed;
deque<Map>dq;
bool v[370000];
int front=0,rear=-1;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int Cantor(int a[],int len){int ans=0;for(int i=0;i<len;i++){int count=0,index=1,f=1;for(int j=i+1;j<len;j++){if(a[i]>a[j])count++;f*=index++;}ans+=count*f;}return ans;
}
int CantorMap(Map map){int b[9];memset(b,0,sizeof(b));for(int i=0;i<3;i++)for(int j=0;j<3;j++)b[i*3+j]=map.arr[i][j];return Cantor(b,9);
}
int main(){memset(v,false,sizeof(v));for(int i=0;i<3;i++)for(int j=0;j<3;j++){int temp;scanf("%d",&temp);if(temp==0){st.x=i,st.y=j;} st.arr[i][j]=temp;}for(int i=0;i<3;i++)for(int j=0;j<3;j++)scanf("%d",&ed.arr[i][j]);v[CantorMap(st)]=true;//list[++rear]=st;dq.push_back(st);int tg=CantorMap(ed);while(!dq.empty()){for(int i=0;i<4;i++){Map map=dq.front();int xx=map.x+dx[i];int yy=map.y+dy[i];if(xx>=0&&yy>=0&&xx<=2&&yy<=2){swap(map.arr[map.x][map.y],map.arr[xx][yy]);map.x=xx;map.y=yy;map.step++;}if(v[CantorMap(map)])continue;if(tg==CantorMap(map)){printf("%d",map.step);return 0;}//list[++rear]=map;dq.push_back(map);v[CantorMap(map)]=true; }//front++;dq.pop_front();}return 0;
}
2初一9班 查智文 20220901 (csy) LV 3 @ 1 周前
做个笔记。 这是STL的做法。#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;struct Map{int x,y,arr[3][3],step;Map(){step=0;}
}st,ed;deque<Map>dq;
bool v[370000];
int front=0,rear=-1;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};int Cantor(int a[],int len){int ans=0;for(int i=0;i<len;i++){int count=0,index=1,f=1;for(int j=i+1;j<len;j++){if(a[i]>a[j])count++;f*=index++;}ans+=count*f;}return ans;
}int CantorMap(Map map){int b[9];memset(b,0,sizeof(b));for(int i=0;i<3;i++)for(int j=0;j<3;j++)b[i*3+j]=map.arr[i][j];return Cantor(b,9);
}int main(){memset(v,false,sizeof(v));for(int i=0;i<3;i++)for(int j=0;j<3;j++){int temp;scanf("%d",&temp);if(temp==0){st.x=i,st.y=j;} st.arr[i][j]=temp;}for(int i=0;i<3;i++)for(int j=0;j<3;j++)scanf("%d",&ed.arr[i][j]);v[CantorMap(st)]=true;dq.push_back(st);int tg=CantorMap(ed);while(!dq.empty()){for(int i=0;i<4;i++){Map map=dq.front();int xx=map.x+dx[i];int yy=map.y+dy[i];if(xx>=0&&yy>=0&&xx<=2&&yy<=2){swap(map.arr[map.x][map.y],map.arr[xx][yy]);map.x=xx;map.y=yy;map.step++;}if(v[CantorMap(map)])continue;if(tg==CantorMap(map)){printf("%d",map.step);return 0;}dq.push_back(map);v[CantorMap(map)]=true; }dq.pop_front();}return 0;
}
2张麟轩 (20220747) LV 4 @ 1 周前
#include<bits/stdc++.h> using namespace std; struct Map{ int x,y,arr[3][3],step; Map(){ step=0; } }st,ed; deque<Map>dq; bool v[370000]; int front=0,rear=-1; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int Cantor(int a[],int len){ int ans=0; for(int i=0;i<len;i++){ int count=0,index=1,f=1; for(int j=i+1;j<len;j++){ if(a[i]>a[j])count++; f*=index++; }ans+=countf; }return ans; } int CantorMap(Map map){ int b[9]; memset(b,0,sizeof(b)); for(int i=0;i<3;i++) for(int j=0;j<3;j++) b[i3+j]=map.arr[i][j]; return Cantor(b,9); } int main(){ memset(v,false,sizeof(v)); for(int i=0;i<3;i++) for(int j=0;j<3;j++){ int temp; scanf("%d",&temp); if(temp0){st.x=i,st.y=j;} st.arr[i][j]=temp; } for(int i=0;i<3;i++) for(int j=0;j<3;j++) scanf("%d",&ed.arr[i][j]); v[CantorMap(st)]=true; dq.push_back(st); int tg=CantorMap(ed); while(!dq.empty()){ for(int i=0;i<4;i++){ Map map=dq.front(); int xx=map.x+dx[i]; int yy=map.y+dy[i]; if(xx>=0&&yy>=0&&xx<=2&&yy<=2){ swap(map.arr[map.x][map.y],map.arr[xx][yy]); map.x=xx; map.y=yy; map.step++; }if(v[CantorMap(map)])continue; if(tgCantorMap(map)){ printf("%d",map.step); return 0; } dq.push_back(map); v[CantorMap(map)]=true; } dq.pop_front(); }return 0; }1潘冠霖 (panguanlin) LV 9 @ 1 周前
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Map{int x,y,arr[3][3],step;Map(){step=0;//步数一开始为0 }
}st,ed,l[370000];//大概有36万种状态
bool v[370000];
int fr=0,rr=-1;//首指针和尾指针
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int Cantor(int a[],int len){//算康托值 int ans=0;for(int i=0;i<len;i++){int c=0,in=1,f=1;for(int j=i+1;j<len;j++){if(a[i]>a[j])c++;f*=in++;}ans+=c*f;}return ans;
}
int CantorMap(Map map){int b[9];memset(b,0,sizeof(b));for(int i=0;i<3;i++){//从0开始(否则下面的转换就要改了) for(int j=0;j<3;j++){b[i*3+j]=map.arr[i][j];//二维转一维 }} return Cantor(b,9);//9个格子
}
int main(){memset(v,0,sizeof(v));for(int i=0;i<3;i++)for(int j=0;j<3;j++){int temp;scanf("%d",&temp);if(temp==0){//找起始位置(0) st.x=i;st.y=j;}st.arr[i][j]=temp;}for(int i=0;i<3;i++){for(int j=0;j<3;j++){scanf("%d",&ed.arr[i][j]);}}v[CantorMap(st)]=1;//标记起点位置(不然可能在起点和下一步之间左右横跳) l[++rr]=st;int tg=CantorMap(ed);//存目标状态 while(fr<=rr){//只要队列里还有东西for(int i=0;i<4;i++){Map map=l[fr];int xx=map.x+dx[i];//控制方向int yy=map.y+dy[i];if(xx>=0&&xx<=2&&yy>=0&&yy<=2){//不越界且不重复(意思是只要能走) swap(map.arr[map.x][map.y],map.arr[xx][yy]);//和分身交换位置 map.x=xx;//更新状态map.y=yy; map.step++;//步数++ }if(v[CantorMap(map)]){//如果之前有过这个目标状态了 continue;//跳过 }if(tg==CantorMap(map)){printf("%d",map.step);return 0;}l[++rr]=map;v[CantorMap(map)]=1;//记录状态(用来判重) }fr++;//出队 } return 0;
}
0谢信宇 LV 5 @ 1 周前
using namespace std;
struct Map{int x,y,arr[3][3],step;//step是步数,arr[3][3]是格子容量 Map(){step=0;//初始化 }
}st,ed,line[100000];//line是list:队列
int dx[4]={0,1,0,-1};//定义方向
int dy[4]={1,0,-1,0};
int front=0,rear=-1;//定义队首和队尾
bool check_same(Map map1,Map map2){//判断是否达到目标状态 for(int i=0;i<3;i++){//遍历输入的3*3格子 for(int j=0;j<3;j++){if(map1.arr[i][j]!=map2.arr[i][j]){//如果达到了map2(目标状态的数字) return false;//那就返回出来1 }}}return true;//否则继续移动宽搜
}
bool check(Map map){//判断下一步和之前有没有重复 for(int i=0;i<=rear;i++){//遍历队列 if(check_same(map,line[i]))//如果在队列中找到了之前的第i步 return false;//那就不要走的啦 }return true;//否则就继续宽搜
}
int main(){for(int i=0;i<3;i++){//输入初始状态 for(int j=0;j<3;j++){int temp;scanf("%d",&temp);st.arr[i][j]=temp;//初始点位的坐标系赋值到temp上if(temp==0){//这是当输入的和输出的一样了的话,就毫不手下留情,干掉!!! st.x=i;//开始的点位赋值到i和j上面(i和j也都是表示点位的) st.y=j;//如法炮制 }}}for(int i=0;i<3;i++){//输入目标状态 for(int j=0;j<3;j++){scanf("%d",&ed.arr[i][j]);}}line[++rear]=st;//入队 while(front<=rear){//当队列正常的时候,判断是不是空队 for(int i=0;i<4;i++){//遍历4个方向 Map map=line[front];//取队首元素 int xx=map.x+dx[i];//定义分身 int yy=map.y+dy[i];//如法炮制 if(xx>=0&&xx<=2&&yy>=0&&yy<=2){//移动范围限定在0到2之间 swap(map.arr[xx][yy],map.arr[map.x][map.y]);//交换位置,表示移动了 map.x=xx;//重新把坐标覆盖上 map.y=yy;//如法炮制 map.step++;//步数+1 if(!check(map)) continue;//判断特殊情况 if(check_same(map,ed)){//如果达到了目标状态 printf("%d",map.step);//输出步数 return 0;//终结 }line[++rear]=map;//下一次入队 }}front++;//出队 }return 0;//The code is over,thank you very much.I am very proud of you can read my solution.
}
相关文章:

一题多解-八数码(万字长文)
16 张炜皓 (ζ͡顾念̶) LV 5 1 周前 在做这道题前,先来认识一下deque双端队列 C STL 中的双端队列 题目连接 使用前需要先引入 头文件。 #include; STL 中对 deque 的定义 // clang-format off template< class T, class Allocator std::allocator class d…...

九种跨域方式实现原理(完整版)
前言 前后端数据交互经常会碰到请求跨域,什么是跨域,以及有哪几种跨域方式,这是本文要探讨的内容。 一、什么是跨域? 1.什么是同源策略及其限制内容? 同源策略是一种约定,它是浏览器最核心也最基本的安…...

fighting
目录Mysqlgroup by和 distinct哪个性能好java觉得Optional类怎么样isEmpty和isBlank的用法区别使用大对象时需要注意什么内存溢出和内存泄漏的区别及详解SpringResource和Autowired的起源既生“Resource”,何生“Autowired”使用Autowired时为什么Idea会曝出黄色警告…...

网络安全日志监控管理
内部安全的重要性 无论大小,每个拥有IT基础设施的组织都容易发生内部安全攻击。您的损失等同于黑客的收益:访问机密数据、滥用检索到的信息、系统崩溃,以及其他等等。专注于网络外部的入侵是明智的,但同时,内部安全也…...

线程池的使用:如何写出高效的多线程程序?
目录1.线程池的使用2.编写高效的多线程程序Java提供了Executor框架来支持线程池的实现,通过Executor框架,可以快速地创建和管理线程池,从而更加方便地编写多线程程序。 1.线程池的使用 在使用线程池时,需要注意以下几点ÿ…...

React 架构流程概览
React 架构流程概览 文章目录React 架构流程概览启动React项目流程分析各部分解析调度器协调器渲染器总结启动React项目 启动项目,并打开 Performance 面板 流程分析 首先找到入口函数 整个 render 下面的调用栈就是首屏渲染要执行的流程。 render 过程大致分为…...

【Linux】进程管理之kill、killall、pkill
一、kill 命令 Linux 中的 kill 命令用来终止指定的进程的运行,是 Linux 下进程管理的常用命令。通常,终止一个前台进程可以使用 CtrlC 键,但是,对于一个后台进程就须用 kill 命令来终止,那就需要先使用 ps、pidof、ps…...

LSTM从入门到精通(形象的图解,详细的代码和注释,完美的数学推导过程)
先附上这篇文章的一个思维导图什么是RNN按照八股文来说:RNN实际上就是一个带有记忆的时间序列的预测模型RNN的细胞结构图如下:softmax激活函数只是我举的一个例子,实际上得到y<t>也可以通过其他的激活函数得到其中a<t-1>代表t-1时…...

19.特殊工具与技术
文章目录特殊工具与技术19.1控制内存分配19.1.1重载new和deleteoperator new接口和operator delete接口malloc函数与free函数19.1.2定位new表达式显式的析构函数调用19.2运行时类型识别(run-time type identification, RTTI)19.2.1dynamic_cast运算符指针类型的dynamic_cast引用…...

518. 零钱兑换 II ——【Leetcode每日一题】
518. 零钱兑换 II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 3…...

django DRF请求访问频率限制
Django REST framework(DRF)提供了一个throttle_classes属性,可以用于限制API的访问频率。它可以防止恶意用户发送大量请求以消耗服务器资源。使用throttle_classes属性,需要在settings.py中配置REST_FRAMEWORK:REST_F…...

二分查找创新性总结
LeetCode题目 704.二分查找35.搜索插入位置69.x 的平方根367.有效的完全平方数34.在排序数组中查找元素的第一个和最后一个位置 二分查找适用范围 可随机访问的数据结构数据已经有序要查找的值只有一个 上述的前四题都可直接使用二分查找,第五题要求查找上限和下限&…...

Java Web 实战 13 - 多线程进阶之 synchronized 原理以及 JUC 问题
文章目录一 . synchronized 原理1.1 synchronized 使用的锁策略1.2 synchronized 是怎样自适应的? (锁膨胀 / 升级 的过程)1.3 synchronized 其他的优化操作锁消除锁粗化1.4 常见面试题二 . JUC (java.util.concurrent)2.1 Callable 接口2.2 ReentrantLock2.3 原子类2.4 线程池…...

【解决】elementui ——tooltip提示在循环中点击一个,同时显示多个的问题!
同时显示多个tooltip——效果图: 点击第一个二维码把循环el-card中所有的tooltip都触发了 解决后效果图: 只显示点击的当前tooltip 解决办法: 通过循环item中定义字段,进行控制tooltip显示隐藏 代码: 页面代码&am…...

SpringBoot-核心技术篇
技术掌握导图 六个大标题↓ 配置文件web开发数据访问单元测试指标指控原理解析 配置文件 1.文件类型 1.1、properties 同以前的properties用法 1.2、yaml 1.2.1、简介 YAML是 “YAML Aint Markup Language”(YAML不是一种标记语言)的递归缩写。在…...

2023还有人不知道kubernetes?| 初步理解kubernetes
文章目录Kubernetes(K8s)一、Openstack&VM1、**认识虚拟化****1.1**、什么是虚拟化**1.2、虚拟化分类**2、OpenStack与KVM、VMWare2.1、OpenStack2.2、KVM2.3、VMWare二、容器&编排技术1、容器发展史1.1、Chroot1.2、FreeBSD Jails1.3、Solaris Zones1.4、LXC1.5、Dock…...

Docker 环境搭建
RabbitMq 安装与启动安装:运行命令:docker pull rabbitmq 默认版本是:latest启动rabbitmq:运行命令:docker run \ # 运行-e RABBITMQ_DETAULT_USERroot \ # 设置用户名-e RABBITMQ_DETAULT_PASS123456 \ # 设置 密码--…...

css实现炫酷充电动画
先绘制一个电池,电池头部和电池的身体 这里其实就是两个div,使用z-index改变层级,电池的身体盖住头部,圆角使用border-radius完成 html部分,完整的css部分在最后 <div class"chargerBox"><div class"ch…...

【Effective C++详细总结】第二章 构造/析构/赋值运算
✍个人博客:https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 📚专栏地址:C/C知识点 📣专栏定位:整理一下 C 相关的知识点,供大家学习参考~ ❤️如果有收获的话,欢迎点赞👍…...

webpack基础
webpack基础 webpack基础目录webpack基础前言Webpack 是什么?Webpack 有什么用?一、webpack的基本使用webpack如何使用文件和文件夹创建创建文件下载依赖二、基本配置5 大核心概念准备 Webpack 配置文件修改配置文件处理样式资源处理图片资源修改输出资源…...

jQuery《一篇搞定》
今日内容 一、JQuery 零、 复习昨日 1 写出至少15个标签 2 写出至少7个css属性font-size,color,font-familytext-algin,background-color,background-image,background-sizewidth,heighttop,bottom ,left ,rightpositionfloatbordermarginpadding 3 写出input标签的type的不…...

Spring Cloud学习笔记【负载均衡-Ribbon】
文章目录什么是Spring Cloud RibbonLB(负载均衡)是什么Ribbon本地负载均衡客户端 VS Nginx服务端负载均衡区别?Ribbon架构工作流程Ribbon Demo搭建IRule规则Ribbon负载均衡轮询算法的原理配置自定义IRule新建MyRuleConfig配置类启动类添加Rib…...

第九章:C语言数据结构与算法初阶之堆
系列文章目录 文章目录系列文章目录前言一、堆的定义二、堆的实现三、堆的接口函数1、初始化2、销毁3、插入4、删除5、判空6、元素个数四、堆排序1、建堆2、排序五、堆的应用——TOPK1、什么是TOPK问题?2、解决方法总结前言 堆就是完全二叉树。 一、堆的定义 我们…...

Mysql架构初识
🥲 🥸 🤌 🫀 🫁 🥷 🐻❄️🦤 🪶 🦭 🪲 🪳 🪰 🪱 🪴 🫐 🫒 🫑…...

字符串函数和内存函数
🍕博客主页:️自信不孤单 🍬文章专栏:C语言 🍚代码仓库:破浪晓梦 🍭欢迎关注:欢迎大家点赞收藏关注 字符串函数和内存函数 文章目录字符串函数和内存函数前言1. 字符串函数介绍1.1 s…...

Web3中文|GPT-4超越GPT-3.5的五大看点
A Beautiful CinderellaDwelling EagerlyFinally Gains HappinessInspiring Jealous KinLove Magically Nurtures Opulent PrinceQuietly RescuesSlipper TriumphsUniting Very WondrouslyXenial Youth Zealously这是一段描述童话故事《灰姑娘》的内容,它出自GPT-4之…...

动态矢量瓦片缓存库方案
目录 前言 二、实现步骤 1.将数据写入postgis数据库 2.将矢量瓦片数据写入缓存库 3.瓦片接口实现 4.瓦片局部更新接口实现 总结 前言 矢量瓦片作为webgis目前最优秀的数据格式,其主要特点就是解决了大批量数据在前端渲染时出现加载缓慢、卡顿的问题࿰…...

628.三个数的最大乘积
给你一个整型数组 nums ,在数组中找出由三个数组成的最大乘积,并输出这个乘积。 示例 1: 输入:nums [1,2,3] 输出:6 示例 2: 输入:nums [1,2,3,4] 输出:24 示例 3: …...

【数据结构】堆和集合笔记
自己写一个堆首先,明确一下,为什么需要堆?>考虑插入,删除,查找的效率。数组,查找,最快是二分查找O(lgN)。但查找完如果要做什么操作,比如删除,就要挪动元素了。所以合…...

java LinkedList 源码分析(通俗易懂)
目录 一、前言 二、LinkedList类简介 三、LinkedList类的底层实现 四、LinkedList类的源码解读 1.add方法解读 : 〇准备工作 。 ①跳入无参构造。 ②跳入add方法。 ③跳入linkList方法。 ④增加第一个元素成功。 ⑤向链表中添加第二个元素。 2.remove方法解读 : 〇准备工…...