题解 P2578 【[ZJOI2005]九数码游戏】
shijunfeng00 · · 题解
竟然没有C++的题解么
来一个C++的题解...
这道题……感觉&细节各种错
首先这个输出状态很麻烦...
从初始状态到末状态是一棵树
从根节点搜子叶要递归很麻烦
所以解决方案有两种
将输入状态定位末状态,初状态为
0 1 2 3 4 5 6 7 8 倒着搜
然后类似
while(!c)
{
cout<<list[c];
c=list[c];
}当然我们定义为 node list[1000000];输出数组, 好像是个链表吧...（还是一棵树,,还是啥链表树,,傻傻分不清啊）
定义个print函数.
然后,,当然,,q.tail的父节点当然是q.head啦
但是STL的queue好像不支持酱紫呀
于是干脆手写队列
和STL用法完全一样
特别注意的就是数组一定要开得贼大
不然无输出,,鬼知道特么要1000000呀
我开的1000，只有40分呢，郁闷了半天
输出当然我是用链表了呀
如果会用指针写链表最好,,节约空间和时间
大概是这么写吧..忘了,一年没用过了
Type*list=new list;
//动态链表建立
Type temp=list;
list=new Type;
list->father=temp;
scanf(list.data)
//遍历
while(list!=NULL)
{
print(list->data);
list=list->father;
}哎呀……废话半天了,,其实我也不会 下面才是重点
#include<iostream>
#include<cstring>
template<typename T_queue> //模板类,
class queue //可以访问下标的队列
{public:
queue(){head=1;tail=0;std::memset(data,0,sizeof(data));}
void push(T_queue a){data[++tail]=a;}
void pop(){if(head<=tail)head++;}
T_queue front(){return data[head];}
T_queue back(){return data[tail];}
bool empty(){return head>tail;}
T_queue data[2000000];
int tail,head;
int father;
};
template<typename T_stack>
class stack //栈
{public:
stack(){std::memset(data,0,sizeof(data));tail=0;}
void push(T_stack a){data[++tail]=a;}
void pop(){if(tail>0)tail--;}
bool empty(){return tail==0;};
T_stack top(){return data[tail];}private:
T_stack data[2000000];
int tail;
};
class node //当前状态最小步数,当前状态.
{public:
int a[10],step;
}s;
/////////////////////////
int temp_stack_list[2000000]; //temp_Type前缀代表Type变量预处理用的临时变量
int f[]={1,1,2,6,24,120,720,5040,40320,326880},book[1000000]; //阶乘打表
queue<node>q;
stack<int*>list; //用法和STL完全一样,,除了下标访问
//////////////////////////以上定义全局变量
using namespace std;
void next(int*a,int i) //两种状态变化方式
{
if(i==1)
{
int temp_a0=a[0];
a[0]=a[3];a[3]=a[6];a[6]=a[7];a[7]=a[8];a[8]=a[5];a[5]=a[2];a[2]=a[1];
a[1]=temp_a0;
return;
}
if(i==2)
{
int temp_a5=a[5];
a[5]=a[4];a[4]=a[3];
a[3]=temp_a5;
return;
}
}
int inline cantor_expansion(int*a) //康拓展开 ,,特殊的hash函数
{
int ans=0;
for(int i=0;i<9;i++)
{
int tmp=0;
for(int j=i+1;j<9;j++)
if(a[i]>a[j])tmp++;
ans+=tmp*f[8-i];
}
return ans;
}
void print(int*a) //打印数组
{
for(int i=0;i<9;i++)
{
cout<<a[i]<<" ";
if((i+1)%3==0)
cout<<endl;
}
}
int main()
{
int end=0;
for(int i=0;i<9;i++)cin>>s.a[i];
if(cantor_expansion(s.a)==0)
{
cout<<0;
return 0;
}
q.push(s);
book[cantor_expansion(s.a)]=1;
while(!q.empty()) //裸的广度优先搜索也能过,,其他的懒得写,,嫌代码不够长么
{
for(int i=2;i>0;--i)
{
node now_status=q.front();
next(now_status.a,i);
now_status.step=q.front().step+1;
if(cantor_expansion(now_status.a)==end)
{
cout<<now_status.step<<endl;
q.push(now_status);
temp_stack_list[q.tail]=q.head;
int p=q.tail;
do
{
list.push(q.data[p].a); //入栈,,把输出顺序颠倒下
p=temp_stack_list[p];
}
while(p);
cout<<endl;
print(list.top());
list.pop();
while(!list.empty())
{
cout<<endl<<endl;
print(list.top()); //输出
list.pop();
}
return 0;
}
if(book[cantor_expansion(now_status.a)]==0)
{
book[cantor_expansion(now_status.a)]=1;
q.push(now_status);
temp_stack_list[q.tail]=q.head; //伪链表
}
}
q.pop();
}
cout<<"UNSOLVABLE";
}