首页 > 代码库 > BFS+康托展开（洛谷1379 八数码难题）

BFS+康托展开（洛谷1379 八数码难题）

2024-10-01 00:34:39   204人阅读

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式：

输入初试状态，一行九个数字，空格用0表示

输出格式：

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入样例#1：
283104765
输出样例#1：
4
思路就是bfs遍历所有的点，用康拓展开进行hash，然后用一个book数组进行判重即可~
注意：string比较不能用==有时候会出Bug。book数组可以和dis合为一体，减少空间，增加代码的可读性~
#include<bits/stdc++.h>using namespace std;int temp[10]={1,1,2,6,24,120,720,5040,5040*9};int dis[500000];int Hash(string s){	int len=s.length();	int ans=0;	for(int i=0;i<len;i++)	{		int tot=0;		for(int j=i+1;j<len;j++)			if(s[j]<s[i]) tot++;		ans+=temp[len-i-1]*tot;	}	return ans;	}string swap(string s,int i,int j){	char c;c=s[i];s[i]=s[j];s[j]=c;	return s;}string move(string s,int k){	int i=s.find(‘0‘);	if(k==1&&i>=3)		s=swap(s,i,i-3);	if(k==2&&i<=5)		s=swap(s,i,i+3);	if(k==3&&i%3!=0)		s=swap(s,i,i-1);	if(k==4&&i%3!=2)		s=swap(s,i,i+1);	return s;}bool Compare(string a,string b){	for(int i=0;i<9;i++)		if(a[i]!=b[i])			return 0;		return 1;}int BFS(string s){	string t("123804765");//目标 	dis[Hash(s)]=1;	queue<string> q;	q.push(s);	while(!q.empty())	{		string u=q.front();q.pop();		if(Compare(u,t)) 		 	return dis[Hash(u)]-1;		for(int i=1;i<=4;i++)		{			string v=move(u,i);			if(dis[Hash(v)]==0)			{				q.push(v);				dis[Hash(v)]=dis[Hash(u)]+1;			}		}	}	return -1;}int main(){	string str;	cin>>str;	cout<<BFS(str)<<endl;	return 0;}

 调试调了5h+也是醉了，我真是一天一天蒟蒻了。。~

BFS+康托展开（洛谷1379 八数码难题）


联系
我们