思路：和迷宫问题一样
迷宫问题：https://www.cnblogs.com/LLLAIH/p/11364937.html
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 #include <stack> 6 #include <algorithm> 7 #include <cmath> 8 #include <map> 9 #define mem(a,b) memset(a,b,sizeof(a)); 10 using namespace std; 11 #define INF 0x3f3f3f3f 12 typedef long long ll; 13 int dir[4][2] = {0,1,0,-1,1,0,-1,0}; 14 const int maxn = 2005; 15 int a,b,c,d,dd; 16 struct Node { 17 int x,y,fa,ans,num,type; 18 Node(){}; 19 Node(int xx,int yy,int faa,int aans,int nnum,int t1):x(xx),y(yy),fa(faa),ans(aans),num(nnum),type(t1){}; 20 }p[maxn]; 21 stack<int>m; 22 bool vis[205][205],flag; 23 void bfs(int ea,int eb) { 24 queue<Node>q; 25 q.push(Node(0,0,0,0,0,0)); 26 vis[ea][eb] = 1; 27 p[0].x = ea,p[0].y = eb,p[0].fa = 0,p[0].ans = 0,p[0].num = 0,p[0].type = 0; 28 int t = 0; 29 while(!q.empty()) { 30 Node temp = q.front(); 31 q.pop(); 32 if(temp.x == c || temp.y == c) { 33 flag = 1; 34 d = temp.ans; 35 dd = temp.num; 36 break; 37 } 38 int fx,fy,ra,rb; 39 //操作１A给Ｂ 40 rb = b - temp.y; 41 if(temp.x > rb) { 42 ra = temp.x - rb; 43 fx = ra; 44 fy = b; 45 46 } 47 else { 48 ra = 0; 49 fx = ra; 50 fy = temp.x + temp.y; 51 } 52 if(!vis[fx][fy]){ 53 t++; 54 vis[fx][fy] = 1; 55 p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 1,p[t].ans = temp.ans+1; 56 q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type)); 57 } 58 59 //操作２ Ｂ给Ａ 60 ra = a - temp.x; 61 if(temp.y > ra) { 62 rb = temp.y - ra; 63 fy = rb; 64 fx = a; 65 } 66 else { 67 rb = 0; 68 fy = rb; 69 fx = temp.x + temp.y; 70 } 71 if(!vis[fx][fy]){ 72 t++; 73 vis[fx][fy] = 1; 74 p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 2,p[t].ans = temp.ans+1; 75 q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type)); 76 } 77 78 //操作３ Ｂ倒完 79 fx = temp.x , fy = 0; 80 if(!vis[fx][fy]){ 81 t++; 82 vis[fx][fy] = 1; 83 p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 3,p[t].ans = temp.ans+1; 84 q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type)); 85 } 86 87 //操作４ Ａ倒完 88 fy = temp.y , fx = 0; 89 if(!vis[fx][fy]){ 90 t++; 91 vis[fx][fy] = 1; 92 p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 4,p[t].ans = temp.ans+1; 93 q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type)); 94 } 95 96 //操作５ Ｂ倒满 97 fx = temp.x , fy = b; 98 if(!vis[fx][fy]){ 99 t++; 100 vis[fx][fy] = 1; 101 p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 5,p[t].ans = temp.ans+1; 102 q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type)); 103 } 104 105 //操作6 A倒满 106 fx = a, fy = temp.y; 107 if(!vis[fx][fy]){ 108 t++; 109 vis[fx][fy] = 1; 110 p[t].x = fx,p[t].y = fy,p[t].fa = temp.num,p[t].num = t,p[t].type = 6,p[t].ans = temp.ans+1; 111 q.push(Node(p[t].x,p[t].y,p[t].fa,p[t].ans,p[t].num,p[t].type)); 112 } 113 114 } 115 } 116 int main() 117 { 118 cin >> a >> b >> c; 119 bfs(a,b); 120 if(flag == 1) { 121 cout << d << endl; 122 int t = dd,tt; 123 m.push(p[t].type); 124 while(1){ 125 t = p[t].fa; 126 tt = p[t].num; 127 if(tt == 0) 128 break; 129 m.push(p[tt].type); 130 } 131 while(!m.empty()){ 132 t = m.top(); 133 m.pop(); 134 if(t == 1) { 135 cout << "POUR(1,2)" << endl; 136 } 137 else if(t == 2) 138 cout << "POUR(2,1)" << endl; 139 else if(t == 3) 140 cout << "DROP(2)" << endl; 141 else if(t == 4) 142 cout << "DROP(1)" << endl; 143 else if(t == 5) 144 cout << "FILL(2)" << endl; 145 else if(t == 6) 146 cout << "FILL(1)" << endl; 147 } 148 } 149 else { 150 cout << "impossible" << endl; 151 } 152 return 0; 153 }