社区讨论

求助,为什么全部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 条回复,欢迎继续交流。

正在加载回复...