社区讨论
求助,为什么全部RE
P1379八数码难题参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2rxqux
- 此快照首次捕获于
- 2023/10/23 18:47 2 年前
- 此快照最后确认于
- 2023/10/23 18:47 2 年前
代码如下,map和队列总不可能爆吧
剩下只有一个3 * 3的矩阵数组和记录上下左右的数组了,别的没有东西越界了吧?
CPP//2023/4/10
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+10;
int num,ans;
struct point{
int r,c;
point()
{
r=0;c=0;
}
point(int ar,int cr)
{
r=ar;c=cr;
}
point friend operator + (point a,point b)
{
return point(a.r+b.r,a.c+b.c);
}
};
point offset[4]={point(0,1),point(1,0),point(-1,0),point(0,-1)};
point baka;
int a;
queue <int> que;
map<int,int> vis;
void bfs()
{
que.push(a);
vis[a]=0;
while(!que.empty())
{
int cnt=que.size();
while(cnt--)
{
int cp=que.front();
int tp=cp;
if(cp==123804765)
{
cout<<vis[123804765]<<endl;
return;
}
int c[3][3];
que.pop();
for (int i=2;i>=0;i--)
{
for (int j=2;j>=0;j--)
{
c[i][j]=tp%10;
tp/=10;
if(c[i][j]==0)
{
baka.r=i;
baka.c=j;
}
}
}
for (int i=0;i<4;i++)
{
int o=0;
point np=baka+offset[i];
if(0<=np.c&&np.c<3&&0<=np.r&&np.r<3)
{
swap(c[np.r][np.c],c[baka.r][baka.c]);
for (int k=0;k<3;k++)
{
for (int j=0;j<3;j++)
{
o=o*10+c[k][j];
}
}
}
//o/=10;
if(!vis.count(o))
{
vis[o]=vis[cp]+1;
//cout<<o<<endl;
que.push(o);
}
swap(c[np.r][np.c],c[baka.r][baka.c]);
}
}
}
}
signed main()
{
cin>>a;
bfs();
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...