学步园

POJ1208 ,来自UVA101题，注意读懂题目意思：

move a onto b:   先将a和b上的积木放回原来的位置，然后再将a放到b上面
move a over b:   先将a上的积木放回到原来的位置，然后将a放到b所在积木堆的顶部（b上的积木不动）
pile a onto b:   先将b上的积木放回原来的位置，再将a和a上的积木放到b上
pile a over b:   将a本身和其上的积木一起搬到到b所在的那堆积木之上

我作为四段读的，str1，num1，str2，num2。但判断的时候，str1只需要判断str[0]，str2只需要判断str2[1]就可以区分命令了.

刚开始题目给的两个例样输出。程序对的，提交后RE，用clock测试了下，发现不可能超时。估计遇到了死循环，于是写了个随机生成测试数据的程序，按照逐步缩小范围的方法，最终确定了问题：原来在确定本题一个关键上——命令有可能是无效的（1.num1和num2相等。2.num1，num2在同一堆上）。我的BUG就在判断同一堆上了。少写了个一半，不严密。修改后AC了。

但奇怪的是POJ AC, UVA不能AC？ 什么问题？随机生成1000组数据都可以测试出来的。

额，纠结于UVA, 这个系统很苛刻。。

#include <stdio.h><br /> #include <string.h></p> <p>typedef struct pile<br /> {<br /> int num;<br /> struct pile *up;<br /> struct pile *down;<br /> }Node;</p> <p>Node a[30];//题目告诉0<n<25,我刚开始设的是1000，保险.<br /> Node init[30];<br /> int n;<br /> int main()<br /> {<br /> int is_column(int n1, int n2);<br /> void Move_Onto(Node *A, Node *B);<br /> void Move_Over(Node *A, Node *B);<br /> void Pile_Onto(Node *A, Node *B);<br /> void Pile_Over(Node *A, Node *B);<br /> Node* Search(int m);<br /> int i, num1, num2;<br /> char str1[5], str2[5];<br /> Node *d, *A, *B;<br /> while (scanf("%d", &n)==1)<br /> {<br /> for (i=0; i<n; i++)<br /> {<br /> a[i].num = i;<br /> a[i].up = NULL;<br /> a[i].down = NULL;<br /> init[i].up = &a[i];<br /> }<br /> while (scanf("%s", str1), str1[0]!='q')<br /> {<br /> scanf("%d%s%d", &num1, str2, &num2);<br /> if (num1==num2 || is_column(num1, num2))<br /> {<br /> continue;<br /> }<br /> A = Search(num1);<br /> B = Search(num2);<br /> if (str1[0]=='m' && str2[1]=='n')//Move_Onto<br /> {<br /> Move_Onto(A, B);<br /> }<br /> else if (str1[0]=='m' && str2[1]=='v')//Move_Over<br /> {<br /> Move_Over(A, B);<br /> }<br /> else if (str1[0]=='p' && str2[1]=='n')//Pile_Onto<br /> {<br /> Pile_Onto(A, B);<br /> }<br /> else//Pile_Over<br /> {<br /> Pile_Over(A, B);<br /> }<br /> }//while(!quit)<br /> for (i=0; i<n; i++)<br /> {<br /> printf("%d:", i);<br /> d = init[i].up;<br /> while(d != NULL)<br /> {<br /> printf(" %d", d->num);<br /> d = d->up;<br /> }<br /> printf("/n");<br /> }<br /> }<br /> return 0;<br /> }</p> <p>Node* Search (int m)<br /> {<br /> Node *d;<br /> int i;<br /> for (i=0; i<n; i++)<br /> {<br /> d = init[i].up;<br /> while (d)<br /> {<br /> if (d->num == m)<br /> {<br /> break;<br /> }<br /> d = d->up;<br /> }<br /> if (d)<br /> {<br /> return d;<br /> }<br /> }<br /> return NULL;<br /> }</p> <p>int is_column(int n1, int n2)<br /> {<br /> Node *A, *B;<br /> A = Search(n1);<br /> B = Search(n2);<br /> while(B->up)<br /> {<br /> if (B->num==A->num)<br /> {<br /> return 1;<br /> }<br /> B = B->up;<br /> }<br /> while(B->down)<br /> {<br /> if (B->num==A->num)<br /> {<br /> return 1;<br /> }<br /> B = B->down;<br /> }<br /> while(A->up)<br /> {<br /> if (B->num==A->num)<br /> {<br /> return 1;<br /> }<br /> A = A->up;<br /> }<br /> while(A->down)<br /> {<br /> if (B->num==A->num)<br /> {<br /> return 1;<br /> }<br /> A = A->down;<br /> }<br /> return 0;<br /> }</p> <p>void Move_Onto(Node *A, Node *B)<br /> {</p> <p> Node *d, *initd;<br /> d = A;<br /> while (d->up)//找A最上面的点<br /> {<br /> d = d->up;<br /> }<br /> while (d!= A)<br /> {<br /> initd = &init[d->num];//找到最上面的点的原来位置<br /> while (initd->up)//找原来位置最上面的点<br /> {<br /> initd = initd->up;<br /> }<br /> initd->up = d;//将A最上面的点挪回原位置的最上面<br /> d = d->down;//准备挪下一个位置<br /> d->up->down = initd;//将原位置最上的点指向新的原位置最上的点<br /> d->up = NULL;<br /> }<br /> d = B;<br /> while (d->up)<br /> {<br /> d = d->up;<br /> }<br /> while (d!= B)<br /> {<br /> initd = &init[d->num];<br /> while (initd->up)<br /> {<br /> initd = initd->up;<br /> }<br /> initd->up = d;<br /> d = d->down;<br /> d->up->down = initd;<br /> d->up = NULL;<br /> }<br /> B->up = A;//A挪到B上<br /> if (A->down == NULL)//如果A为最下面的一个点,则只剩头结点<br /> {<br /> init[A->num].up = NULL;<br /> }<br /> else<br /> {<br /> A->down->up = NULL;<br /> }<br /> A->down = B;<br /> }</p> <p>void Move_Over(Node *A, Node *B)<br /> {<br /> Node *d, *initd;<br /> d = A;<br /> while (d->up)<br /> {<br /> d = d->up;<br /> }<br /> while (d!= A)<br /> {<br /> initd = &init[d->num];<br /> while (initd->up)<br /> {<br /> initd = initd->up;<br /> }<br /> initd->up = d;<br /> d = d->down;<br /> d->up->down = initd;<br /> d->up = NULL;<br /> }<br /> d = B;<br /> while (d->up)<br /> {<br /> d = d->up;<br /> }<br /> d->up = A;<br /> if (A->down == NULL)<br /> {<br /> init[A->num].up = NULL;<br /> }<br /> else<br /> {<br /> A->down->up = NULL;<br /> }<br /> A->down = d;<br /> }</p> <p>void Pile_Onto(Node *A, Node *B)<br /> {<br /> Node *d, *initd;<br /> d = B;<br /> while (d->up)<br /> {<br /> d = d->up;<br /> }<br /> while (d!= B)<br /> {<br /> initd = &init[d->num];<br /> while (initd->up)<br /> {<br /> initd = initd->up;<br /> }<br /> initd->up = d;<br /> d = d->down;<br /> d->up->down = initd;<br /> d->up = NULL;<br /> }<br /> B->up = A;<br /> if (A->down == NULL)<br /> {<br /> init[A->num].up = NULL;<br /> }<br /> else<br /> {<br /> A->down->up = NULL;<br /> }<br /> A->down = B;<br /> }</p> <p>void Pile_Over(Node *A, Node *B)<br /> {<br /> Node *d;<br /> d = B;<br /> while (d->up)<br /> {<br /> d = d->up;<br /> }<br /> d->up = A;<br /> if (A->down == NULL)<br /> {<br /> init[A->num].up = NULL;<br /> }<br /> else<br /> {<br /> A->down->up = NULL;<br /> }<br /> A->down = d;<br /> }</p> <p>

下面是数据生成器:

#include <stdio.h><br /> #include <stdlib.h><br /> #include <time.h></p> <p>double random()<br /> {<br /> return (double) rand() / RAND_MAX;<br /> }</p> <p>int rando(int m)<br /> {<br /> return (int)(random() * (m-1) + 0.5);<br /> }<br /> int main()<br /> {<br /> int n, i, m, ci;<br /> freopen("in.txt", "w", stdout);<br /> srand(time(NULL));<br /> scanf("%d", &n);<br /> for (i=0; i<n; i++)<br /> {<br /> m = rand()%50+1;<br /> printf("%d/n", m);<br /> ci = rand()%50+1;<br /> while (ci--)<br /> {<br /> if (rand()%2 ==0)<br /> {<br /> printf("move");<br /> }<br /> else<br /> {<br /> printf("pile");<br /> }<br /> printf(" ");<br /> printf("%d",rando(m));<br /> printf(" ");<br /> if (rand()%2 ==0)<br /> {<br /> printf("onto");<br /> }<br /> else<br /> {<br /> printf("over");<br /> }<br /> printf(" ");<br /> printf("%d",rando(m));<br /> printf("/n");<br /> }<br /> printf("quit/n");<br /> }<br /> return 0;<br /> }<br />