POJ 3414 Pots ( BFS , 打印路径 ）
题意：
给你两个空瓶子，只有三种操作
一、把一个瓶子灌满
二、把一个瓶子清空
三、把一个瓶子里面的水灌到另一个瓶子里面去（倒满之后要是还存在水那就依然在那个瓶子里面，或者被灌的瓶子有可能没满）
思路：BFS，打印路径时需技巧。
//G++ 840K0MS#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <stack>#include <queue>#include <cmath>#include <map>#include <vector>#include <algorithm>#define MIN(A,B) ((A)<(B)?(A):(B))#define DEBUG puts("Hello world!");#define N 110using namespace std ;bool visit[N][N] ;struct node{ int x , y ; int step ;}pos , next ;struct way{ int x , y ; int stept ;}before[N][N] ;voidPrint_Path ( int x , int y ){ stack<int>st ; while ( x != 0 || y != 0 ) { st.push ( before[x][y].stept ) ; int temp_x , temp_y ; temp_x = before[x][y].x ; temp_y = before[x][y].y ; x = temp_x ; y = temp_y ; } while ( !st.empty() ) { switch ( st.top() ) { case 1: printf("DROP(1)\n"); break; case 2: printf("DROP(2)\n"); break; case 3:printf("FILL(1)\n"); break; case 4:printf("FILL(2)\n"); break; case 5:printf("POUR(1,2)\n"); break; case 6:printf("POUR(2,1)\n"); break; } st.pop ( ) ; } return ;}voidModify ( node * const p , int const x , int const y , int const step ){ p->x = x ; p->y = y ; p->step = step ; return ;}boolBFS ( int const A , int const B , int const C ){ queue <node>q ; next.x = 0 ; next.y = 0 ; next.step = 0 ; visit[0][0] = true ; q.push(next) ; while ( !q.empty( ) ) { pos = q.front ( ) ; q.pop ( ) ; if ( C == pos.x || C == pos.y ) { printf ("%d\n" ,pos.step ) ; Print_Path ( pos.x , pos.y ) ; //DEBUG return true ; } if ( !visit[0][pos.y] && 0 != pos.x ) //case 1 : DROP(1) { Modify ( & next , 0 , pos.y , pos.step + 1 ) ; q.push ( next ) ; visit[0][pos.y] = true ; before[0][pos.y] = ( struct way ) { pos.x , pos.y,1 } ; } if ( !visit[pos.x][0] && 0 != pos.y ) //case 2 : DROP(2) { Modify ( & next , pos.x , 0 , pos.step + 1 ) ; q.push ( next ) ; visit[pos.x][0] = true ; before[pos.x][0] = ( struct way ) { pos.x , pos.y , 2 } ; } if ( !visit[A][pos.y] && A != pos.x ) //case 3 : FILL(1) { Modify ( & next , A , pos.y , pos.step + 1 ) ; q.push ( next ) ; visit[A][pos.y] = true ; before[A][pos.y] = ( struct way ) { pos.x , pos.y , 3 } ; } if ( !visit[pos.x][B] && B != pos.y ) //case 4 : FILL(2) { Modify ( & next , pos.x , B , pos.step + 1 ) ; q.push ( next ) ; visit[next.x][next.y] = true ; before[pos.x][B] = ( struct way ) { pos.x , pos.y , 4 } ; } if ( pos.x > 0 && pos.y < B ) //case 5 : POUR(1,2) { int temp ; temp = MIN ( pos.x , B - pos.y ) ; if ( !visit[pos.x-temp][pos.y+temp] ) { Modify ( & next , pos.x - temp , pos.y + temp , pos.step + 1 ) ; q.push ( next ) ; visit[next.x][next.y] = true ; before[next.x][next.y] = ( struct way ) {pos.x , pos.y,5} ; } } if ( pos.x < A && pos.y > 0 ) //case 6: POUR(2,1) { int temp ; temp = MIN ( pos.y , A - pos.x ) ; if ( !visit[pos.x+temp][pos.y-temp] ) { Modify ( & next , pos.x + temp , pos.y - temp , pos.step + 1 ) ; q.push ( next ) ; visit[next.x][next.y] = true ; before[next.x][next.y] = (struct way ){pos.x , pos.y , 6} ; } } } return false ;}intmain ( ){ int A ,B , C ; while ( EOF != scanf ("%d%d%d" , & A , & B , & C ) ) { if ( !BFS ( A , B , C ) ) { printf ("impossible\n") ; } memset ( visit , 0 , sizeof ( visit ) ) ; } return 0 ;}