分析:
在讀完題目之后，首先想到就是歸納所有可行的操作，包括：
1. 裝滿A
2. 裝滿B
3. 清空A
4. 清空B
5. 將A中的水倒入B中
6. 將B中的水倒入A中
如果要找到最少操作，使用BFS；如果要找到所有可能的操作，使用DFS
代碼:
/*
* 題目:
* 給你一個3升的杯子和一個5升的(杯子是沒有刻度的)，要你取4升水來(水可以無限取)，請問該如何操作。
*
* 泛化:
* 給你一個m升的杯子和一個n升的(杯子是沒有刻度的)，要你取target升水來（水可以無限取），請問該如何操作.
*
* 思路:
* 搜索: BFS or DFS
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define CAPACITY_LIMIT 15 /* the maximum value of capacity of cups */
#define STATE_LIMIT ((CAPACITY_LIMIT+1)*(CAPACITY_LIMIT+1))
#define GET_BYTE_HIGH(state) (((state) & 0xF0)>>4)
#define GET_BYTE_LOW(state) ((state) & 0x0F)
#define SET_BYTE_HIGH(state, value) do { ((state) &= 0x0F); \
((state) |= ((value)<<4)); } while(0)
#define SET_BYTE_LOW(state, value) do { ((state) &= 0xF0); \
((state) |= (value)); } while(0)
int m, n, target;
const char *ops_name[] = {
"FILL A",
"FILL B",
"EMPTY A",
"EMPTY B",
"FROM A TO B",
"FROM B TO A" };
struct State {
unsigned char state;
char op;
char prev;
} queue[STATE_LIMIT], tmp;
int head, tail;
char visited[STATE_LIMIT];
void
bfs_inner(int a, int b, int op)
{
int c;
tmp.op = op;
tmp.state = queue[head].state;
switch(op) {
case 0:
/* FILL A */
SET_BYTE_HIGH(tmp.state, m);
break;
case 1:
/* FILL B */
SET_BYTE_LOW(tmp.state, n);
break;
case 2:
/* EMPTY A */
SET_BYTE_HIGH(tmp.state, 0);
break;
case 3:
/* EMPTY B */
SET_BYTE_LOW(tmp.state, 0);
break;
case 4:
/* FROM A TO B */
c = a > (n-b) ? (n-b) : a;
SET_BYTE_LOW(tmp.state, b+c);
SET_BYTE_HIGH(tmp.state, a-c);
break;
case 5:
/* FROM B TO A */
c = b > (m-a) ? (m-a) : b;
SET_BYTE_HIGH(tmp.state, a+c);
SET_BYTE_LOW(tmp.state, b-c);
break;
}
if(!visited[tmp.state]) {
visited[tmp.state] = 1;
++tail;
memcpy(queue+tail, &tmp, sizeof(struct State));
}
}
void
print_bfs_ret(int index)
{
if(index == -1)
return;
print_bfs_ret(queue[index].prev);
printf("%s:\tA(%d), B(%d)\n", queue[index].prev==-1 ? "Init State" : ops_name[queue[index].op],
GET_BYTE_HIGH(queue[index].state), GET_BYTE_LOW(queue[index].state));
}
int
bfs()
{
int a, b, op;
memset(visited, 0, sizeof(char)*STATE_LIMIT);
memset(queue, 0, sizeof(struct State)*STATE_LIMIT);
head = -1;
tail = 0;
/* init state, push into queue */
queue[tail].state = 0;
queue[tail].op = -1;
queue[tail].prev = -1;
visited[queue[tail].state] = 1;
while(head < tail) { /* while queue's not empty */
++head;
a = GET_BYTE_HIGH(queue[head].state);
b = GET_BYTE_LOW(queue[head].state);
if(a==target || b==target) /* find it */
return 1;
tmp.prev = head;
for(op=0; op<6; ++op) {
bfs_inner(a, b, op);
}
}
return 0;
}
int
state_cal(int state, int op, int a, int b)
{
int c;
switch(op) {
case 0:
/* FILL A */
SET_BYTE_HIGH(state, m);
break;
case 1:
/* FILL B */
SET_BYTE_LOW(state, n);
break;
case 2:
/* EMPTY A */
SET_BYTE_HIGH(state, 0);
break;
case 3:
/* EMPTY B */
SET_BYTE_LOW(state, 0);
break;
case 4:
/* FROM A TO B */
c = a > (n-b) ? (n-b) : a;
SET_BYTE_LOW(state, b+c);
SET_BYTE_HIGH(state, a-c);
break;
case 5:
/* FROM B TO A */
c = b > (m-a) ? (m-a) : b;
SET_BYTE_HIGH(state, a+c);
SET_BYTE_LOW(state, b-c);
break;
default:
state = -1;
}
return state;
}
int dfs_visited[STATE_LIMIT];
int record[STATE_LIMIT];
void
dfs(int depth, int state)
{
int a, b, op;
a = GET_BYTE_HIGH(state);
b = GET_BYTE_LOW(state);
if(a==4 || b==4) {
/* result print */
int i;
for(i=0; i<depth; ++i)
printf("%s\n", ops_name[record[i]]);
printf("--------------------------------------\n");
return;
}
dfs_visited[state] = 1;
for(op=0; op<6; ++op) {
int nstate = state_cal(state, op, a, b);
if(!dfs_visited[nstate]) {
record[depth] = op;
dfs(depth+1, nstate);
}
}
dfs_visited[state] = 0;
}
int
main(int argc, char **argv)
{
printf("Enter capacity of A: ");
scanf("%d", &m);
printf("Enter capacity of B: ");
scanf("%d", &n);
printf("Enter target: ");
scanf("%d", &target);
dfs(0, 0);
return;
}