简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)

【题目描述】

两个容器，分别能装下A升水和B升水，并且可以进行以下操作

FILL(i)        将第i个容器从水龙头里装满(1 ≤ i ≤ 2);

DROP(i)        将第i个容器抽干

POUR(i,j)      将第i个容器里的水倒入第j个容器（这次操作结束后产生两种结果，一是第j个容器倒满并且第i个容器依旧有剩余，二是第i个容器里的水全部倒入j中，第i个容器为空）

现在要求你写一个程序，来找出能使其中任何一个容器里的水恰好有C升，找出最少操作数并给出操作过程

【输入】

有且只有一行，包含3个数A,B,C（1<=A,B<=100,C<=max(A,B)）

【输出】

第一行包含一个数表示最小操作数K

随后K行每行给出一次具体操作，如果有多种答案符合最小操作数，输出他们中的任意一种操作过程，如果你不能使两个容器中的任意一个满足恰好C升的话，输出“impossible”

解题思路

可以将两个水杯中的水量当做一个“二维地图”，当进行一步操作时，两个杯子里的水量在之前出现过了，就不需要进行这个操作，之前的地图是往四个方向遍历，而这里是往水杯能进行的六个操作遍历。

用的是 bfs 和队列的知识。

因为是用的栈，首先队头 head，队尾 tail，用数组 a 和数组 b 记录栈中水杯 A和水杯 B 的水量，数组 ans 记录其下标对应的栈元素已经进行的操作数，数组 f[i][j] 用来存放栈中以 i 为下标的元素先前的进行的具体操作。

一共是六个操作，用一个循环遍历每一次的操作，用 book 数组记录是否出现过，如果 book [x][y]==0，就把它添加到队尾，一个结点遍历六个操作后，将队头移出队列。

对于往杯子里倒水，是要原杯子里水没满的情况下进行，而倒水出来时，要保证杯子里有水，否则没有意义。

对于每一步操作都要先判断能够进行该操作的条件。

代码如下：

#include
int n, m, t;
int head, tail;
int book[10010][10010];
int ans[10010];
int f[10010][10010];
int a[10010], b[10010];//记录栈的a，b水杯中的值
int flag = 0,k=0;
void bfs(int x, int y)
{int i, j;if (k == 1)return;if (x == t || y == t){flag = 1;printf("%d\n",ans[head]);for (i = 1; i <= ans[head]; i++){if (f[head][i] == 1)printf("FILL(1)\n");if (f[head][i] == 2)printf("FILL(2)\n");if (f[head][i] == 3)printf("DROP(1)\n");if (f[head][i] == 4)printf("DROP(2)\n");if (f[head][i] == 5)printf("POUR(1,2)\n");if (f[head][i] == 6)printf("POUR(2,1)\n");}k = 1;return;}for (i = 1; i <= 6; i++){//往A倒水if (i == 1 && x != n && book[n][y] == 0){book[n][y] = 1;tail++;ans[tail] = ans[head] + 1;//当前操作数//把当前A,B水量入栈a[tail] = n;b[tail] = y;//将栈顶元素的操作步骤存入入栈的元素的操作步骤for (j = 1; j <= ans[head]; j++)f[tail][j] = f[head][j];//将刚刚的第i个操作存入f[tail][ans[tail]] = i;}//往B倒水if (i == 2 && y != m && book[x][m] == 0){book[x][m] = 1;tail++;ans[tail] = ans[head] + 1;a[tail] = x;b[tail] = m;for (j = 1; j <= ans[head]; j++)f[tail][j] = f[head][j];f[tail][ans[tail]] = i;}//把A的水抽干if (i == 3 && x != 0 && book[0][y] == 0){book[0][y] = 1;tail++;ans[tail] = ans[head] + 1;a[tail] = 0;b[tail] = y;for (j = 1; j <= ans[head]; j++)f[tail][j] = f[head][j];f[tail][ans[tail]] = i;}//把B的水抽干if (i == 4 && y != 0 && book[x][0] == 0){book[x][0] = 1;tail++;ans[tail] = ans[head] + 1;a[tail] = x;b[tail] = 0;for (j = 1; j <= ans[head]; j++)f[tail][j] = f[head][j];f[tail][ans[tail]] = i;}//把A的水倒入Bif (i == 5 && x != 0 && y != m&&book[0][x+y]==0){book[0][x + y] = 1;if (x + y <= m){tail++;a[tail] = 0;b[tail] = x + y;}else{tail++;a[tail] = x + y - m;b[tail] = m;}ans[tail] = ans[head] + 1;for (j = 1; j <= ans[head]; j++)f[tail][j] = f[head][j];f[tail][ans[tail]] = i;}//把B的水倒入Aif (i == 6 && x != n && y != 0 && book[x + y][0] == 0){book[x + y][0] = 1;if (x + y <= n){tail++;a[tail] = x + y;b[tail] = 0;}else{tail++;a[tail] = n;b[tail] = x + y - n;}ans[tail] = ans[head] + 1;for (j = 1; j <= ans[head]; j++)f[tail][j] = f[head][j]; f[tail][ans[tail]] = i;}}head++;if (head <= tail)bfs(a[head], b[head]);elsereturn;return;
}
int main()
{int i, j;scanf("%d %d %d", &n, &m, &t);book[0][0] = 1;bfs(0, 0);if (flag == 0)printf("impossible");return 0;
}