首页 > ACM题库 > HDU-杭电 > hdu 2269 Cross The River待解决[解题报告]C++
2014
01-04

hdu 2269 Cross The River待解决[解题报告]C++

Cross The River

问题描述 :

Most of you may have played the game called crossing the river. This game is: a farmer carries a wolf, a sheep and a basket of grass to cross a river , but only one boat can be used . And everytime ,at most one thing and the farmer can take the boat to cross the river because only the farmer can use the boat . But if the farmer is not in, the wolf will eat the sheep ,the sheep will eat the grass . You are asked to help the farmer cross the river without losing anything . I think most of you can find the way.
But this time , the problem is more difficult . The farmer now takes more things, and some of them may eat the other thing if the farmer is not in . At the same time , the boat is becoming more bigger and it may be able to carry more things .You are asked to help the farmer to find a way to cross the river as soon as possible without losing anything.

输入:

Each test case will contain three integers n(1=<n<=11) ,m(m<=100) and t (1=<t<=5). n stands for the number of things the farmer carries , m stands for the number of dangerous condition that some things may be eaten by others ,t stands for the number of things the boat can carry besides the farmer.
Then n line follows , stands for the name of the n things . Then name will only contains lowercase letters ,and the length will not exceed 20.
Then m line follows ,each line contains several things ,which means if these things stay together without the farmer,some thing will been eaten.

输出:

Each test case will contain three integers n(1=<n<=11) ,m(m<=100) and t (1=<t<=5). n stands for the number of things the farmer carries , m stands for the number of dangerous condition that some things may be eaten by others ,t stands for the number of things the boat can carry besides the farmer.
Then n line follows , stands for the name of the n things . Then name will only contains lowercase letters ,and the length will not exceed 20.
Then m line follows ,each line contains several things ,which means if these things stay together without the farmer,some thing will been eaten.

样例输入:

2 1 1
sheep
wolf
sheep wolf

样例输出:

3
Hint
Hint At first the farmer carrys the sheep to cross the river ,then the farmer return back without carrying anything, then carrying the wolf to cross the river.


  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3