时间限制：1 秒
内存限制：32 兆
特殊判题：是
提交：744
解决：502
- 题目描述：
有一个农夫带一只羊、一筐菜和一只狼过河.
果没有农夫看管，则狼要吃羊，羊要吃菜.
但是船很小，只够农夫带一样东西过河。
问农夫该如何解此难题？
- 输入：
题目没有任何输入。
- 输出：
题目可能有种解决方法，求出步骤最少的解决方法，
按顺序输出农夫想把羊、菜、狼全部运过河需要哪几个步骤。
如果需要将羊带过河去则输出“sheep_go”。
如果需要将羊带回来则输出“sheep_come”。
如果需要将菜带过河去则输出“vegetable_go”。
如果需要将菜带回来则输出“vegetable_come”。
如果需要将狼带过河去则输出“wolf_go”。
如果需要将狼带回来则输出“wolf_come”。
如果需要空手返回则输出“nothing_come”。
如果需要空手过河则输出“nothing_go”。
每输出一种方案，输出一行“succeed”。
- 样例输入：
- 样例输出：
- 提示：
题目可能有多组解决方法，每种方法输出后要再空一行。
一种方法中的多句话，每句话占一行。
思路：
4个变量分别表示人和所带东西的状态，在河对岸则为1，否则为0。那么该题的初始状态是(0, 0, 0, 0)，终止状态是(1, 1, 1, 1)。
由于要求的是最短步骤，应该用BFS。状态变换的规则是每次只能农夫或带任意东西过河。
我只用了1个变量，其低4位表示4个人或东西的状态。开始想取巧，但对位操作并不熟练，因而并未更优。
代码：
#include <stdio.h>
#include <string.h> #define M 16 int beginState;
int endState;
int state[M], v[M];
int best[M], lest; void init()
{
beginState = 0;
endState = M-1;
state[0] = beginState;
memset(v, 0, sizeof(v));
v[beginState] = 1;
lest = M+1;
} int bit(int i, int b)
{
return (i>>b)&1;
} int move(int count)
{
int s = state[count-1];
if (s == endState)
{
if (count < lest)
{
lest = count;
//printf("=====\n");
for (int i=0; i<count; i++)
{
best[i] = state[i];
// printf("%d%d%d%d\n", bit(best[i],3), bit(best[i],2),
// bit(best[i],1), bit(best[i],0));
}
//printf("=====\n");
}
return count;
}
if (count == M)
return M+1;
int i, t;
for (i=0; i<M; i++)
{
if (v[i])
continue;
if (s/8 == i/8)
continue;
if (s/8 == 1)
{
t = s-8;
int flag = 0;
if (t == i)
flag = 1;
if (bit(t,0) && t-1 == i)
flag = 1;
if (bit(t,1) && t-2 == i)
flag = 1;
if (bit(t,2) && t-4 == i)
flag = 1;
if (flag == 0)
continue;
}
else
{
t = s+8;
int flag = 0;
if (t == i)
flag = 1;
if (bit(i,0) && t+1 == i)
flag = 1;
if (bit(i,1) && t+2 == i)
flag = 1;
if (bit(i,2) && t+4 == i)
flag = 1;
if (flag == 0)
continue;
}
if (bit(i,3)^bit(i,1))
{
if ((bit(i,3)^bit(i,0)) || (bit(i,3)^bit(i,2)))
continue;
}
state[count] = i;
v[i] = 1;
int step = move(count+1);
if (step <= M)
return step;
v[i] = 0;
}
return M+1;
} void printBest()
{
int s0, s, t;
s0 = best[0];
for (int i=1; i<lest; i++)
{
s = best[i];
if (bit(s,3))
{
t = s-s0;
if (t == 8)
printf("nothing_go\n");
if (bit(t, 0))
printf("vegetable_go\n");
if (bit(t, 1))
printf("sheep_go\n");
if (bit(t, 2))
printf("wolf_go\n");
}
else
{
t = s0-s;
if (t == 8)
printf("nothing_come\n");
if (bit(t, 0))
printf("vegetable_come\n");
if (bit(t, 1))
printf("sheep_come\n");
if (bit(t, 2))
printf("wolf_come\n");
}
s0 = s;
}
printf("succeed\n\n");
} int main(void)
{
init(); move(1); printBest(); return 0;
}
/**************************************************************
Problem: 1204
User: liangrx06
Language: C
Result: Accepted
Time:0 ms
Memory:908 kb
****************************************************************/