Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
BFS+注释/* 每一个状态下,对应有6种操作 1,fill A 2,fill B 3,drop A 4,drop B 5,pour A-->B 此时有两种可能 5-1,A可以全部倒入B中 A中剩余0,B中剩余A+B 5-2,A不可以全部倒入B中 A中剩余A+B-b ,B中满 6,pour B-->A 此时和5一样,同样有两种可能 */ #include<cstdio> #pragma warning (disable:4996) using namespace std; const int MAX = 110; int a, b, c; //记录两个容器的大小及最终目标 int step; //最终的步数 bool flag; //能否找到最终状态的标志 int lastIndex; //标记符合条件的状态在队列中的位置 int visit[MAX][MAX]; //状态数组,若是相同的状态,则不需要再加入队列 struct Status { int k1, k2; int step; int op; //操作的方法 int fatherPosition; //上一个状态在队列中的位置,方便找到上一个状态,这样就可以获取上一个状态操作的方法 }queue[MAX*MAX]; void bfs() { Status now, next; //当前状态,下一个状态 int head=0, tail=1; //头指针、尾指针 now.k1 = 0; now.k2 = 0; now.op = 0; now.step = 0; now.fatherPosition = 0; //将当前状态设置成初始状态 queue[0] = now; //当前状态入队 visit[0][0] = 1; while (head < tail) //只要队列不空,则继续入队、出队操作 { //头指针所指的出队,出队的状态为当前状态 now = queue[head]; head++; //出队后,头指针往后移动一个 //对于当前的状态,让所有可能的下一个状态入队,一个状态的所有可能的下一个状态共有6种 for (int i = 1; i <= 6; i++) { switch (i) { case 1: //fill(a) next.k1 = a; next.k2 = now.k2; break; case 2: //fill(b) next.k1 = now.k1; next.k2 = b; break; case 3: //drop(a) next.k1 = 0; next.k2 = now.k2; break; case 4: //drop(b) next.k1 = now.k1; next.k2 = 0; break; case 5: //pour(a, b) a--->b if ((now.k1 + now.k2) <= b) { next.k1 = 0; next.k2 = now.k1 + now.k2; } else { next.k1 = (now.k1 + now.k2) - b; next.k2 = b; } break; case 6: //pour(b,a) b--->a if ((now.k1 + now.k2) <= a) { next.k1 = now.k1 + now.k2; next.k2 = 0; } else { next.k1 = a; next.k2 = (now.k1 + now.k2) - a; } break; } next.op = i; //记录下一个状态的操作 //printf("head=%d tail=%d i=%d (%d,%d)\n", head, tail, i, next.k1, next.k2); //判断头、尾指针以及入队出队是否正确 if (!visit[next.k1][next.k2]) //如果下一个状态未曾被加入到队列中 { //printf("****\n"); //判断是否入队 visit[next.k1][next.k2] = 1; //标记 next.step = now.step + 1; //将该状态的步数加1 next.fatherPosition = head - 1; //它爸爸就是当前状态(刚出队的),因为出队后头指针往后移动了一个,所以这个减一,表示它爸在队列中的位置 queue[tail] = next; //将下一个状态加入队列尾部,有状态入队后,尾指针往后移动一个 tail++; //判断这个状态是否是最终状态,若是,直接结束了,若不是,加入队列 if (next.k1 == c || next.k2 == c) { flag = true; //标志位置真 step = next.step; //更新最终步数 lastIndex = tail - 1; //若这个状态是最终状态,则将这个状态在队列中的位置标记一下 return; //找到后,直接退出bfs } } } } } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt","w",stdout); while (scanf("%d %d %d", &a, &b, &c) != EOF) { step = 0; flag = false; int id[MAX*MAX]; //记录到达最终状态过程中,每一个状态在队列中的位置 for (int i = 0; i < MAX; i++) //状态数组清零 for (int j = 0; j < MAX; j++) visit[i][j] = 0; //printf("!!!!!\n"); bfs(); //printf("!!!!!\n"); if (flag) { printf("%d\n", step); //最后一个状态在队列中的下标是lastIndex id[step] = lastIndex; for (int i = step - 1; i >= 1; i--) //通过fatherPosition参数从最后一个状态开始往前找它的父状态,并且记录每个状态的操作 { id[i] = queue[id[i + 1]].fatherPosition; //id[i+1]表示后一个状态在队列中的下标 } for (int i = 1; i <= step; i++) { switch (queue[id[i]].op) //所有有效的状态的操作 { case 1: printf("FILL(1)\n"); break; case 2: printf("FILL(2)\n"); break; case 3: printf("DROP(1)\n"); break; case 4: printf("DROP(2)\n"); break; case 5: printf("POUR(1,2)\n"); break; case 6: printf("POUR(2,1)\n"); break; } } } else printf("impossible\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator