博文
UVa 101 解题小结——要认真读题！切记！切记！
|||
开刷第二题UVa101，这道题是一个关于数据结构的问题，还好之前看过一些相关的东东，感觉可能用stack更简单一些，我一开始却2B兮兮的用了一个双向链表，不过感觉差不多，相比较之下在四种操作中，各有优势。
https://blog.sciencenet.cn/blog-723765-645280.html
上一篇：UVa 100 解题小结——坑，遍地都是坑！
下一篇：UVa 102 解题小结——多亏n只是3，要不就跪了
这题是一个关于block移来移去的问题，具体的问题参见原网站
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37 （因为我觉得以我的表达能力是说不清的）
我的解题思路是构建一个多维双向链表，每个节点包括自身的一个值，一个指向下一个元素的指针，一个指向前一个的指针，参见源码中的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，要不就跪了
