我比较懒,直接用string记录路径,可是是因为这个地方超时。。。
#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; string path; }q[20000],ans;7 bool bfs(){ int head,rear; head=rear=0; q[rear].i=0; q[rear].step=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]){ q[rear].i=a; q[rear].j=tmp.j; q[rear].step=tmp.step+1; q[rear++].path=tmp.path+"FILL(1)\n"; visit[a][tmp.j]=true; } if(!visit[tmp.i][b]){ q[rear].i=tmp.i; q[rear].j=b; q[rear].step=tmp.step+1; q[rear++].path=tmp.path+"FILL(2)\n"; 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]){ q[rear].i=t1; q[rear].j=t2; q[rear].step=tmp.step+1; q[rear++].path=tmp.path+"POUR(2,1)\n"; visit[t1][t2]=true; } if(x>b){ t1=tmp.i-(b-tmp.j); t2=b; }else{ t2=x; t1=0; } if(!visit[t1][t2]){ q[rear].i=t1; q[rear].j=t2; q[rear].step=tmp.step+1; q[rear++].path=tmp.path+"POUR(1,2)\n"; visit[t1][t2]=true; } if(!visit[0][tmp.j]){ q[rear].i=0; q[rear].j=tmp.j; q[rear].step=tmp.step+1; q[rear++].path=tmp.path+"DROP(1)\n"; visit[0][tmp.j]=true; } if(!visit[tmp.i][0]){ q[rear].i=tmp.i; q[rear].j=0; q[rear].step=tmp.step+1; q[rear++].path=tmp.path+"DROP(2)\n"; visit[tmp.i][0]=true; } } return false; } 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; cout<<ans.path; }else{ cout<<"impossible"<<endl; } return 0; }