中国站长之家网站,模板网站是什么,官方网站管理办法,网站开发师招聘给你两个容量分别为 A 升和 B 升的罐子。可以进行以下操作#xff1a;
FILL(i) 从水龙头向罐子 i#xff08;1 ≤ i ≤ 2#xff09;灌满水#xff1b;DROP(i) 把罐子 i 的水倒空#xff1b;POUR(i,j) 从罐子 i 向罐子 j 倒水#xff1b;此操作后#x…给你两个容量分别为 A 升和 B 升的罐子。可以进行以下操作
FILL(i) 从水龙头向罐子 i1 ≤ i ≤ 2灌满水DROP(i) 把罐子 i 的水倒空POUR(i,j) 从罐子 i 向罐子 j 倒水此操作后要么罐子 j 满了罐子 i 可能还有水要么罐子 i 空了所有水都倒到罐子 j 里。
编写一个程序找出能使其中一个罐子中恰好有 C 升水的最短操作序列。
输入
第一行包含三个整数 A、B 和 C。这些数都在 1 到 100 的范围内且 C ≤ max(A,B)。
输出
输出的第一行必须包含操作序列的长度 K。接下来的 K 行分别描述一个操作。如果有多个最短长度的操作序列输出其中任意一个。如果无法达到期望结果输出文件的第一行必须包含单词 ‘impossible’。
示例
InputOutput 3 5 4 6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
解题思路
本题有3总操作但操作的对象不同一共有6种不同操作题目求最短显然用bfs搜索更好一点
我们在找到终点还要回溯其走过的点这里可以在结构体里面增加一个变量记录是由哪个点来的
最后记得逆序输出答案
#includestdio.h
#includestring.h
struct bbffss {int x;//横坐标int y;//纵坐标int f;//从哪个点来的int s;char str[15];
}q[10000005];
int a, b, c, k 0, top 0, sum 0, flag 0;
int book[101][101], m, n;
char str1[] FILL(0);
char str2[] DROP(0);
char str3[] POUR(0,0);
char sy[100000][15];
void sss(int x, int y,int tail)
{switch (x){case 1:strcpy(q[tail].str, str1);q[tail].str[5] y;break;case 2:strcpy(q[tail].str, str2);q[tail].str[5] y;break;case 3:strcpy(q[tail].str, str3);if (y 1){q[tail].str[5] 1;q[tail].str[7] 2;}else{q[tail].str[5] 2;q[tail].str[7] 1;}break;}
}
void bfs()
{int hard 1, tail 2, tx, ty;book[0][0] 1;q[1].x 0; q[1].y 0;q[1].f 0; q[1].s 0;while (hard tail){for (int j 1; j 2; j)//两种不同的操作对象{for (int i 1; i 3; i)//三种操作方式{//根据操作方式和对象的不同switch (i){case 1:if (j 1){tx a;ty q[hard].y;}else{tx q[hard].x;ty b;}break;case 2:if (j 1){tx 0;ty q[hard].y;}else{tx q[hard].x;ty 0;}break;case 3:m q[hard].x;n q[hard].y;if (j 1){if (b - n m){tx 0;ty n m;}else{tx m - (b - n);ty b;}}else{if (a - m n){tx n m;ty 0;}else{tx a;ty n - (a - m);}}break;}if (book[tx][ty] 1)continue;book[tx][ty] 1;//标记存在这种情况//入队操作q[tail].x tx; q[tail].y ty;q[tail].f hard; q[tail].s q[hard].s 1;sss(i, j, tail);if (tx c || ty c)//判断是否到达指定容量{int ff tail;sum q[tail].s;while (ff ! 0){strcpy(sy[top], q[ff].str);ff q[ff].f;}flag 1;return;}tail;}}hard;}
}
int main()
{scanf(%d %d %d, a, b, c);//输入a,b,cbfs();//进行搜索if (flag 1)//有答案进行输出{printf(%d\n, sum);for (int i top - 1; i 1; i--)//逆序输出printf(%s\n, sy[i]);}else//没有答案printf(impossible\n);return 0;
}
