POJ 3414. Pots
1. 题目
http://poj.org/problem?id=3414
Pots
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 12107 Accepted: 5110 Special Judge Description
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:
- FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
- DROP(i) empty the pot i to the drain;
- POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).
Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.
Input
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
Output
The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.
Sample Input
3 5 4Sample Output
6 FILL(2) POUR(2,1) DROP(1) POUR(2,1) FILL(2) POUR(2,1)Source
Northeastern Europe 2002, Western Subregion
2. 思路
小学奥数题。给出两个容积分别为A和B的壶，求是否能得到容积为C的水，如果可行，需要给出过程。
BFS。总共有六种操作，A倒满、B倒满、A倒空、B倒空、A倒B、B倒A，每次操作后得到一个状态（包括A的余量、B的余量、操作名、当前步数、上一步操作），如果这个状态中A和B的余量在之前没有出现过，则入队（使用数组history[a][b]记录A壶有a升水、B壶有b升水的状态是否出现过）。直到有一个壶得到C升水，回溯得到操作过程；队列为空则无法实现。
3.代码
#include <stdlib.h>
#include <stdio.h>
#define MAX_VOLUME 100
#define OP_FILL_1 1
#define OP_FILL_2 2
#define OP_DROP_1 3
#define OP_DROP_2 4
#define OP_POUR_1_2 5
#define OP_POUR_2_1 6
#define NOT_PRESENTED 0
#define PRESENTED 1
typedef unsigned char History[MAX_VOLUME + 1][MAX_VOLUME + 1];
typedef struct StatusRecord {
int a;
int b;
int operation;
int step;
int lastId;
} Status;
void solveE1e();
int findSolution(int volA, int volB, int goal, Status status[]);
void initHistory(History history);
void setStatus(Status *current, int a, int b, int operation, int step, int lastId);
void printSolution(Status status[], int last);
int main() {
solveE1e();
// system("pause");
return 0;
}
Status status[(MAX_VOLUME + 1) * (MAX_VOLUME + 1)];
void solveE1e() {
int volA, volB, goal, last;
scanf("%d %d %d", &volA, &volB, &goal);
if (goal == 0) {
printf("0\n");
} else {
last = findSolution(volA, volB, goal, status);
if (last == -1) {
printf("impossible\n");
} else {
printSolution(status, last);
}
}
}
History history;
int findSolution(int volA, int volB, int goal, Status status[]) {
int front = 0, rear = 0;
Status current, next;
initHistory(history);
setStatus(&status[rear++], 0, 0, 0, 0, -1);
history[0][0] = PRESENTED;
while (front < rear) {
current = status[front++];
if (current.a == goal || current.b == goal) {
return front - 1;
}
// OP_FILL_1
setStatus(&next, volA, current.b, OP_FILL_1, current.step + 1, front - 1);
if (history[next.a][next.b] == NOT_PRESENTED) {
status[rear++] = next;
history[next.a][next.b] = PRESENTED;
}
// OP_FILL_2
setStatus(&next, current.a, volB, OP_FILL_2, current.step + 1, front - 1);
if (history[next.a][next.b] == NOT_PRESENTED) {
status[rear++] = next;
history[next.a][next.b] = PRESENTED;
}
// OP_DROP_1
setStatus(&next, 0, current.b, OP_DROP_1, current.step + 1, front - 1);
if (history[next.a][next.b] == NOT_PRESENTED) {
status[rear++] = next;
history[next.a][next.b] = PRESENTED;
}
// OP_DROP_2
setStatus(&next, current.a, 0, OP_DROP_2, current.step + 1, front - 1);
if (history[next.a][next.b] == NOT_PRESENTED) {
status[rear++] = next;
history[next.a][next.b] = PRESENTED;
}
// OP_POUR_1_2
if (current.a + current.b <= volB) {
setStatus(&next, 0, current.a + current.b, OP_POUR_1_2, current.step + 1, front - 1);
} else {
setStatus(&next, current.a + current.b - volB, volB, OP_POUR_1_2, current.step + 1, front - 1);
}
if (history[next.a][next.b] == NOT_PRESENTED) {
status[rear++] = next;
history[next.a][next.b] = PRESENTED;
}
// OP_POUR_2_1
if (current.a + current.b <= volA) {
setStatus(&next, current.a + current.b, 0, OP_POUR_2_1, current.step + 1, front - 1);
}
else {
setStatus(&next, volA, current.a + current.b - volA, OP_POUR_2_1, current.step + 1, front - 1);
}
if (history[next.a][next.b] == NOT_PRESENTED) {
status[rear++] = next;
history[next.a][next.b] = PRESENTED;
}
}
return -1;
}
void initHistory(History history) {
int i, j;
for (i = 0; i <= MAX_VOLUME; ++i) {
for (j = 0; j <= MAX_VOLUME; ++j) {
history[i][j] = NOT_PRESENTED;
}
}
}
void setStatus(Status *current, int a, int b, int operation, int step, int lastId) {
current->a = a;
current->b = b;
current->operation = operation;
current->step = step;
current->lastId = lastId;
}
unsigned char opSeq[(MAX_VOLUME + 1) * (MAX_VOLUME + 1)];
void printSolution(Status status[], int last) {
int step, statusId, op, i;
step = status[last].step;
printf("%d\n", step);
statusId = last;
while (step--) {
op = status[statusId].operation;
opSeq[step] = op;
statusId = status[statusId].lastId;
}
for (i = 0; i < status[last].step; ++i) {
op = opSeq[i];
switch (op) {
case OP_FILL_1:
printf("FILL(1)\n"); break;
case OP_FILL_2:
printf("FILL(2)\n"); break;
case OP_DROP_1:
printf("DROP(1)\n"); break;
case OP_DROP_2:
printf("DROP(2)\n"); break;
case OP_POUR_1_2:
printf("POUR(1,2)\n"); break;
case OP_POUR_2_1:
printf("POUR(2,1)\n"); break;
default:
break;
}
}
}