可以说搞这个题搞了近5个小时,中间睡了个午觉整理了下思路才有心情再敲的,不得不说poj在极限数据这方面真的很Nb,而且我更没有想到string的操作会这么慢,有TLE的同学可以尝试一下自己记录path;
bfs---无剪枝扩张。。。
code如下:
#include <iostream> #include <fstream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <string.h> #include <vector> #include <bitset> #include <cmath> #include <queue> #include <stack> #include <set> #include <ctime> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FU(i,a) for(int i(1); i <= (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FORD(i,a,b) for(int i(a);i >= (b); i--) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const double pi = acos(-1.0); const int maxn = 2000; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; int a,b,c; bool visit[200][200]; struct state{ int i,j,step; int pre; short op; }q[20000],ans; bool bfs(){ int head,rear; head=rear=0; q[rear].i=0; q[rear].step=0; q[rear].pre=-1; q[rear].op=0; q[rear++].j=0; visit[0][0]=false; while(head<rear){ state tmp=q[head++]; if(tmp.i==c || tmp.j==c){ ans=tmp; return true; } if(!visit[a][tmp.j]){ //FILL(1); q[rear].i=a; q[rear].j=tmp.j; q[rear].step=tmp.step+1; q[rear].pre=head-1; q[rear++].op=1; visit[a][tmp.j]=true; } if(!visit[tmp.i][b]){ //FILL(2); q[rear].i=tmp.i; q[rear].j=b; q[rear].step=tmp.step+1; q[rear].pre=head-1; q[rear++].op=2; visit[tmp.i][b]=true; } int x=tmp.i+tmp.j,t1,t2; if(x>a){ t2=tmp.j-(a-tmp.i); t1=a; }else{ t1=x; t2=0; } if(!visit[t1][t2]){ //POUR(2,1); q[rear].i=t1; q[rear].j=t2; q[rear].step=tmp.step+1; q[rear].pre=head-1; q[rear++].op=3; visit[t1][t2]=true; } if(x>b){ t1=tmp.i-(b-tmp.j); t2=b; }else{ t2=x; t1=0; } if(!visit[t1][t2]){ //POUR(1,2); q[rear].i=t1; q[rear].j=t2; q[rear].step=tmp.step+1; q[rear].pre=head-1; q[rear++].op=4; visit[t1][t2]=true; } if(!visit[0][tmp.j]){ //DROP(1); q[rear].i=0; q[rear].j=tmp.j; q[rear].step=tmp.step+1; q[rear].pre=head-1; q[rear++].op=5; visit[0][tmp.j]=true; } if(!visit[tmp.i][0]){ //DROP(2); q[rear].i=tmp.i; q[rear].j=0; q[rear].step=tmp.step+1; q[rear].pre=head-1; q[rear++].op=6; visit[tmp.i][0]=true; } } return false; } void print(state end){ if(end.pre==-1) return ; else{ print(q[end.pre]); if(end.op==1) puts("FILL(1)"); else if(end.op==2) puts("FILL(2)"); else if(end.op==3) puts("POUR(2,1)"); else if(end.op==4) puts("POUR(1,2)"); else if(end.op==5) puts("DROP(1)"); else puts("DROP(2)"); } } int main() { SD(a); SD(b); SD(c); if(a % 2 == 0 && b % 2 == 0 && c % 2 != 0) { cout << "impossible" << endl; return 0; } if(c > a && c > b) { cout << "impossible" << endl; return 0; } bool flag=bfs(); if(flag){ cout<<ans.step<<endl; print(ans); }else{ cout<<"impossible"<<endl; } return 0; }