題目大意
給兩個空杯子，告訴我們杯子的容量朵诫，然后給出幾種操作辛友。
操作1 ： DROP(x) 意思是將x杯子中的水杯倒空。
操作2 ： FILL(x) 意思是把x杯子中裝滿剪返。
操作3 ： POUR(x,y) 意思是將x杯子中的水全部倒到y(tǒng)中去废累。
然后給定一個k值邓梅，問經(jīng)過最小多少次操作能有一個水杯里的水有k這么多。輸出操作次數(shù)及方式九默。
如果沒法滿足震放，輸出impossible。
樣例輸入
3 5 4
樣例輸出
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
分析
這題用bfs搜一遍驼修，不要用dfs答案其實沒那么深殿遂，深搜沒必要而且會炸
最麻煩的是輸出路徑，用爸爸兒子的辦法倒著找就好了乙各。
代碼如下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#define CLR(x) memset(x,0,sizeof(x))
#define LL long long
#define debug() printf("!!!!!!!!\n");
using namespace std;
int k,con;
struct node{
int v1,v2;
int s1,s2;
int id;
int pre;
char c[20];
}now,ans[500];
char str[1000][20];
int vis[105][105];
int bfs(){
queue<node> q;
q.push(now);
while(!q.empty()){
node r = q.front();
q.pop();
int tmp1 = r.s1 , tmp2 = r.s2;
if(r.s1 == k || r.s2 == k){
//printf("%d %d\n",r.s1,r.s2);
//printf("r.id = %d\n",r.id);
return r.id;
}
//=============================================
//DROP1;
if(r.s1){
r.s1 = 0;
if(vis[r.s1][r.s2] == 0){
vis[r.s1][r.s2] = 1;
con++;
ans[con] = r;
ans[con].pre = r.id;
ans[con].id = con;
char c[20] = {"DROP(1)\0"};
strcpy(ans[con].c , c);
q.push(ans[con]);
}
r.s1 = tmp1;
}
//FILL1;
r.s1 = r.v1;
if(vis[r.s1][r.s2] == 0){
vis[r.s1][r.s2] = 1;
con++;
ans[con] = r;
ans[con].pre = r.id;
ans[con].id = con;
char c[20] = {"FILL(1)\0"};
strcpy(ans[con].c , c);
q.push(ans[con]);
}
r.s1 = tmp1;
//POUR(1,2)
int cha = r.v2 - r.s2 ;
if(r.s1 >= cha){
r.s1 -= cha;
r.s2 = r.v2;
}
else{
r.s2 += r.s1;
r.s1 = 0;
}
if(vis[r.s1][r.s2] == 0){
vis[r.s1][r.s2] = 1;
vis[r.s1][r.s2] = 1;
con++;
ans[con] = r;
ans[con].pre = r.id;
ans[con].id = con;
char c[20] = {"POUR(1,2)\0"};
strcpy(ans[con].c,c);
q.push(ans[con]);
}
r.s1 = tmp1;
r.s2 = tmp2;
//=========================================
//DROP(2)
if(r.s2){
r.s2 = 0;
if(vis[r.s1][r.s2] == 0){
vis[r.s1][r.s2] = 1;
con++;
ans[con] = r;
ans[con].pre = r.id;
ans[con].id = con;
char c[20] = {"DROP(2)\0"};
strcpy(ans[con].c , c);
q.push(ans[con]);
}
r.s2 = tmp2;
}
//FILL(2)
r.s2 = r.v2;
if(vis[r.s1][r.s2] == 0){
vis[r.s1][r.s2] = 1;
con++;
ans[con] = r;
ans[con].pre = r.id;
ans[con].id = con;
char c[20] = {"FILL(2)\0"};
strcpy(ans[con].c,c);
q.push(ans[con]);
}
r.s2 = tmp2;
//POUR(2,1)
cha = r.v1 - r.s1 ;
if(r.s2 >= cha){
r.s2 -= cha;
r.s1 = r.v1;
}
else{
r.s1 += r.s2;
r.s2 = 0;
}
if(!vis[r.s1][r.s2]){
vis[r.s1][r.s2] = 1;
vis[r.s1][r.s2] = 1;
con++;
ans[con] = r;
ans[con].pre = r.id;
ans[con].id = con;
char c[20] = {"POUR(2,1)\0"};
strcpy(ans[con].c , c);
q.push(ans[con]);
}
r.s1 = tmp1;
r.s2 = tmp2;
}
return -1;
}
int main(){
CLR(ans);
CLR(str);
cin >> now.v1 >> now.v2 >> k;
now.pre = -1;
now.id = 0;
now.c[0] = 0;
CLR(vis);
con = 0;
int x = bfs();
//printf("%d\n",x);
int cnt = 0;
if(x != -1){
while(ans[x].pre != 0){
strcpy(str[cnt],ans[x].c);
x = ans[x].pre;
cnt++;
//printf(" x = %d , cnt = %d\n",x,cnt);
}
strcpy(str[cnt],ans[x].c);
printf("%d\n",cnt+1);
for(int i = cnt ; i >= 0 ; i--){
printf("%s\n",str[i]);
}
}
else{
printf("impossible\n");
}
}
