USACO Shuttle Puzzle

这是一道很坑人的题，有两种方法，一种是BFS，另外一种是“观察法”。

本人用的是BFS，思路是从最初状态开始扩展状态树，当发现目标状态时停止搜索即可（此题没有多个解的情况，USACO给出的提示是多余的，并且如果发现目标状态后不停止很可能会超出内存限制）。

不过当N大于7时，上面的算法会超出时间限制，因此，需要剪枝。可以发现，要使步骤最少，白色珠子只能向右侧移动，黑色只能向左侧移动。加上这个限制后，所有数据均可以在0.2s内通过。

在每个队列元素中，储存了到达它的上一个节点指针和所做得变化，因此输出结果并不难。

此外判重使用散列表和自己胡编的散列函数，使用链表处理冲突。

一个小插曲：最初在USACO上评测的时候，到弟4组数据就超时了。后来发现删去输出到stderr的语句就顺利通过了。

“观察法”请看NOCOW上的题解，http://www.nocow.cn/index.php/USACO/shuttle

代码如下：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define E 0
005 #define W 1
006 #define B 2
007
008 typedef struct Node   //Node in queue
009 {
010     int op;
011     struct Node *prev;
012     char state[30];
013     int empty;
014 }Node;
015
016 typedef struct HNode   //Hash node
017 {
018     char state[30];
019     struct HNode *next;
020 }HNode;
021
022 int N;
023 HNode *table[5897];
024 Node queue[150000];
025 long head,tail;
026
027 void traceback(Node *final);   //store steps in array solution
028
029 void enqueue(Node v)
030 {
031     queue[tail ++] = v;
032 }
033
034 Node * dequeue()
035 {
036     return &queue[head ++];
037 }
038
039 long hash(Node * elem)
040 {
041     long r = 0;
042     int i;
043     for(i = 0;i <= 2 * N;i ++)
044     {
045         r *= 3;
046         r += elem->state[i];
047         r %= 5897;
048     }
049     return r;
050 }
051
052 void insert(Node *elem)   //insert a state into hash table
053 {
054     HNode *p;
055     p = malloc(sizeof(HNode));
056     memcpy(p->state,elem->state,30);
057     p->next = table[hash(elem)];
058     table[hash(elem)] = p;
059 }
060
061 int visit(Node *elem)   //check if the state is already visited
062 {
063     HNode *p;
064     for(p = table[hash(elem)];p != NULL;p = p->next)
065     {
066         if(memcmp(p->state,elem->state,30) == 0)    return 1;
067     }
068     return 0;
069 }
070
071 long targethash;
072 char targetstate[30];
073 void init()   //creat initial and target
074 {
075     Node start;
076     start.empty = N;
077     start.op = 0;
078     start.prev = NULL;
079     int i;
080     //initial state
081     for(i = 0;i < N;i ++)    start.state[i] = 1;
082     for(i = N + 1;i <= 2 * N;i ++)    start.state[i] = 2;
083     start.state[N] = 0;
084     head = tail = 0;
085     enqueue(start);
086     insert(&start);
087     //target state
088     for(i = 0;i < N;i ++)    targetstate[i] = start.state[i] = 2;
089     for(i = N + 1;i <= 2 * N;i ++)    targetstate[i] = start.state[i] = 1;
090     targethash = hash(&start);
091 }
092
093 int istarget(Node *elem)
094 {
095     if(hash(elem) == targethash && memcmp(targetstate,elem->state,2 * N + 1) == 0)
096     {
097         return 1;
098     }
099     return 0;
100 }
101
102 void BFS()
103 {
104     Node *now,next;
105     while(head < tail)
106     {
107         now = dequeue();
108         if(istarget(now))
109         {
110             traceback(now);
111             return;
112         }
113         //move right
114         if(now->empty > 0 && now->state[now->empty - 1] == W)
115         {
116             memcpy(&next,now,sizeof(Node));
117             next.state[next.empty] = next.state[next.empty - 1];
118             next.state[next.empty - 1] = 0;
119             next.op = next.empty - 1;
120             next.prev = now;
121             next.empty --;
122             if(!visit(&next))
123             {
124                 enqueue(next);insert(&next);
125             }
126         }
127         //move left
128         if(now->empty < 2 * N && now->state[now->empty + 1] == B)
129         {
130             memcpy(&next,now,sizeof(Node));
131             next.state[next.empty] = next.state[next.empty + 1];
132             next.state[next.empty + 1] = 0;
133             next.op = next.empty + 1;
134             next.prev = now;
135             next.empty ++;
136             if(!visit(&next))
137             {
138                 enqueue(next);insert(&next);
139             }
140         }
141         //jump right
142         if(now->empty > 1 && now->state[now->empty - 2] == W && now->state[now->empty - 1] != now->state[now->empty - 2])
143         {
144             memcpy(&next,now,sizeof(Node));
145             next.state[next.empty] = next.state[next.empty - 2];
146             next.state[next.empty - 2] = 0;
147             next.op = next.empty - 2;
148             next.prev = now;
149             next.empty -= 2;
150             if(!visit(&next))
151             {
152                 enqueue(next);insert(&next);
153             }
154         }
155         //jump left
156         if(now->empty < 2 * N - 1 && now->state[now->empty + 2] == B && now->state[now->empty + 1] != now->state[now->empty + 2])
157         {
158             memcpy(&next,now,sizeof(Node));
159             next.state[next.empty] = next.state[next.empty + 2];
160             next.state[next.empty + 2] = 0;
161             next.op = next.empty + 2;
162             next.prev = now;
163             next.empty += 2;
164             if(!visit(&next))
165             {
166                 enqueue(next);insert(&next);
167             }
168         }
169     }
170 }
171
172 int minstep;
173 int solution[200];    //in reverse order
174 int cnt = 0;
175 void traceback(Node *final)
176 {
177     Node *p = final;
178     int i;
179     for(i = 0;p != NULL;p = p->prev,i ++)
180     {
181         solution[i] = p->op;
182     }
183     minstep = i - 1;
184 }
185
186 void pt()
187 {
188     int i;
189     int cc = 0;
190     for(i = minstep - 1;i >= 0;i --)
191     {
192         cc ++;
193         printf("%d",solution[i] + 1);
194         if(cc == 20 && i != 0)
195         {
196             printf("\n");
197             cc = 0;
198         }
199         else if(i != 0)
200             printf(" ");
201     }
202     printf("\n");
203 }
204
205 int main()
206 {
207     freopen("shuttle.in","r",stdin);
208     freopen("shuttle.out","w",stdout);
209     scanf("%d",&N);
210     init();
211     BFS();
212     pt();
213     fclose(stdout);
214     return 0;
215 }