「八数码问题」5997 Problem C 【宽搜入门】8数码难题

八数码问题

问题 C: 【宽搜入门】8数码难题

时间限制: 20 Sec 内存限制: 128 MB

提交: 63 解决: 13

题目描述

初始状态的步数就算1，哈哈

输入：第一个3*3的矩阵是原始状态，第二个3*3的矩阵是目标状态。

输出：移动所用最少的步数

Input

2 8 3

1 6 4

7 0 5

1 2 3

8 0 4

7 6 5

Output

经验总结

这题可以说。。。有点坑了。。。折腾了几天，倒不是说这一题的坑多。。是自己身上的坑多º·(˚ ˃̣̣̥᷄⌓˂̣̣̥᷅ )‧º·

先说说这个题目的坑吧，首先题目说的有点不清楚，害的我这种小白都不知道要干什么0.0 后来百度了才知道，原来0是代表空格，只能移动空格位置，最终得到第二个矩阵的状态，还有一个坑，八数码问题可能是无解的，所以，这题竟然没说无解的时候要输出什么？可能是。。测试数据中就没有无解的吧，测试完发现，果真木有。。（\#-_-)\┯━┯

再说说这个问题，这个问题本身。。。难度倒是不大，还在构思范围之内，手贱搜了一下网上的代码。。才发现，卧槽？还可以这样解？？此处贴一大神的帖子 7种方法求解八数码问题看完了这个帖子，妈耶。。脑阔疼。。映射方法三种（数组+哈希+map），搜索方法三种（BFS+DBFS+A*），而且一个比一个高效，让我等小白大开眼界，然后，我看到其中的康托展开，于是乎又手贱去搜了个帖子康托展开和逆康托展开 emmm这个倒是不难，可以理解( ´´ิ∀´ิ` ) get了一个新技能~ 后来关于八数码问题无解的判别条件也去搜了搜就搜到了一个大佬的帖子~判断N 数码是否有解牛人总结归并排序万事俱备，只欠提交啦~

然鹅。。事情并没有我想象的那么顺利。。看了代码，又去查了一些代码规范以及自己不懂的撸码方式，比如：

1、在for循环中++i与i++到底有没有区别，只放在for循环里，区别不大，但是要明白他们的区别i++是先用后加，++i是先加后用，所以区别就是。。。看下面代码你就懂啦。

模拟a=i++;
temp=i;
i=i+1;
a=temp;

模拟a=++i;
i=i+1;
a=i;

i++需要多一个临时存储空间，操作上也要多一步赋值，所以效率上，++i要更快一些。

2、结构体可以内置初始化函数，这样的话生成一个新结构体就可以像C++中的构造函数一样写啦~，关于内置操作运算符的使用，我也学习到了。。。就比如：

struct node
{
	int cost;
	bool operator<(const node &no)const
	{
		return cost>no.cost;
	}
}

struct node
{
	int cost;
	friend bool operator<(const node &n1,const node &n2)const
	{
		return n1.cost>n2.cost;
	}
}

这两个代码的效果是一样的，但是表达上，参数数量不同，const修饰位置不同，而且一个是内置函数一个是友元函数，区别很多。。。但这里强调一下，const常量修饰，防止其更改参数内容，加&引用是为了高效，因为你又不准备修改它，所以传一个原参的地址指针过来，效率就很高，内存方面占用更小。

最后说说自己的问题吧，马虎！！while(scanf("%d",&n))竟然没有发现少加了一个取反位运算符~，导致输出一直超限。。。找不到原因，还以为是算法思想出了问题，就十分崩溃。。。

最终实现代码，是参考了上面大神的A*+BFS+map，这样比单纯的用BFS+数组标记在时间和空间上都快了至少两个数量级。。。最后奉上代码。。。大神请轻喷0.0

正确代码

#include <cstdio>
#include <map>
#include <queue>

using namespace std;
char goal[10];
int start,termination;
struct node
{
	int step,cost,num,pos;
	node(int n,int s,int p)
	{
		num=n;
		step=s;
		pos=p;
		compute();
	}
	bool operator<(const node &no)const
	{
		return cost>no.cost;
	}
	void compute()
	{
		int c=0;
		char temp[10];
		sprintf(temp,"%09d",num);
		for(int i=0;i<9;i++)
		{
			if(temp[i]!=goal[i])
				c++;
		}
		cost=step+c;
	}
};
int director[9][4]={{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}};
void swap(char str[],int a,int b)
{
	char temp=str[a];
	str[a]=str[b];
	str[b]=temp;
}
bool judge(char a[],char b[])
{
	int r1=0,r2=0;
	for(int i=0;i<9;i++)
	{
		if(a[i]=='0')
			continue;
		for(int j=0;j<i;j++)
		{
			if(a[j]=='0')
				continue;
			if(a[j]>a[i])
				r1++;
		}
	}
	for(int i=0;i<9;i++)
	{
		if(b[i]=='0')
			continue;
		for(int j=0;j<i;j++)
		{
			if(b[j]=='0')
				continue;
			if(b[j]>b[i])
				r2++;
		}
	}
	if(r1%2==r2%2)
		return true;
	else
		return false;
}
priority_queue<node> p;
map<int,bool> mp;
int combine(int num,int pos)
{
	char temp[10];
	int temp1;
	node s(num,0,pos);
	p.push(s);
	mp[num]=true;
	while(!p.empty())
	{
		s=p.top();
		p.pop();
		sprintf(temp,"%09d",s.num);
		for(int i=0;i<4;i++)
		{
			if(director[s.pos][i]!=-1)
			{
				swap(temp,s.pos,director[s.pos][i]);
				sscanf(temp,"%d",&temp1);
				if(s.num==termination)
					return s.step+1;
				if(mp.count(temp1)==0)
				{
					node r(temp1,s.step+1,director[s.pos][i]);
					p.push(r);
					mp[temp1]=true;
				}
				swap(temp,s.pos,director[s.pos][i]);
			}
		}
	}
}

int main()
{
	int n,pos;
	char temp[10];
	while(~scanf("%d",&n))
	{

		start=n;
		for(int i=0;i<8;i++)
		{
			scanf("%d",&n);
			start=start*10+n;
		}
		sprintf(temp,"%09d",start);
		for(int i=0;i<9;i++)
			if(temp[i]=='0')
				pos=i;
		termination=0;
		for(int i=0;i<9;i++)
		{
			scanf("%d",&n);
			termination=termination*10+n;
		}
		sprintf(goal,"%09d",termination);
		if(judge(temp,goal))
		{
			int count=0;
			count=combine(start,pos);
			printf("%d\n",count);
		}
		else
		{
			printf("-1\n");
		}
	}
	return 0;
}

5997 Problem C 【宽搜入门】8数码难题