开刷第二题UVa101,这道题是一个关于数据结构的问题,还好之前看过一些相关的东东,感觉可能用stack更简单一些,我一开始却2B兮兮的用了一个双向链表,不过感觉差不多,相比较之下在四种操作中,各有优势。
这题是一个关于block移来移去的问题,具体的问题参见原网站
我的解题思路是构建一个多维双向链表,每个节点包括自身的一个值,一个指向下一个元素的指针,一个指向前一个的指针,参见源码中的block_type的数据结构。根据这个结构,定义两个数组pos和block,pos为多维双向链表的头指针,block为初始的block。之后通过改变指针进行调整。
源码:
# include <iostream>
# include <string>
using namespace std;
struct block_type
{
int num;
struct block_type *next;
struct block_type *pre;
}block[25],pos[25];
void retu(struct block_type &a)
{//归还函数
if(a.next==NULL)
return;
else
{
struct block_type* t,*m;
t=a.next;
retu(*t);
m=pos+t->num;
while(m->next!=NULL)
{
m=m->next;
}
t->pre=m;
m->next=t;
t->next=NULL;
}
}
bool is_same(struct block_type* a,struct block_type* b)
{//检测是否位于同一个pos
while(a->next!=NULL)
{
if(a->next==b)
return true;
a=a->next;
}
while(b->next!=NULL)
{
if(b->next==a)
return true;
b=b->next;
}
return false;
}
int main()
{
int num;//数据总数
cin>>num;
for(int i =0; i<num;++i)//初始化
{
block[i].num=i;
block[i].next=NULL;
block[i].pre=pos+i;
pos[i].next=block+i;
}
string com1,com2;
int n1,n2;
cin>>com1;
while(com1!="quit")//主要循环
{
cin>>n1>>com2>>n2;
if(n1==n2)//是否a=b
{
cin>>com1;
continue;
}
if(is_same(&block[n1],&block[n2]))//是否位于同一区域
{
cin>>com1;
continue;
}
if(com1=="move")
{
retu(block[n1]);
block[n1].next=NULL;
}
if(com2=="onto")
{
retu(block[n2]);
block[n2].next=NULL;
}
struct block_type *p1;
struct block_type *b1,*b2;
b1=&block[n1];
b2=&block[n2];
p1=b1->pre;
p1->next=NULL;
while(b2->next!=NULL)
b2=b2->next;
b2->next=b1;
b1->pre=b2;
cin>>com1;
}
for(int i =0;i<num;++i)//输出
{
cout<<i<<":";
if(pos[i].next!=NULL)
{
struct block_type t2;
t2=*pos[i].next;
cout<<" "<<t2.num;
while(t2.next!=NULL)
{
t2=*t2.next;
cout<<" "<<t2.num;
}
}
cout<<endl;
}
return 0;
}
心得体会:一定要看清题,题目中最后给出了两种错误输入是可以ignore的,我一看是没有注意,结果纠结了好久…………
仔细读题!!!!
https://blog.sciencenet.cn/blog-723765-645280.html
上一篇:
UVa 100 解题小结——坑,遍地都是坑!下一篇:
UVa 102 解题小结——多亏n只是3,要不就跪了