首页 > ACM题库 > 九度OJ > 九度-1204-农夫、羊、菜和狼的故事[解题代码]
2013
12-13

九度-1204-农夫、羊、菜和狼的故事[解题代码]

题目来源:2008年华中科技大学计算机保研机试真题

题目描述:

有一个农夫带一只羊、一筐菜和一只狼过河.
果没有农夫看管,则狼要吃羊,羊要吃菜.
但是船很小,只够农夫带一样东西过河。
问农夫该如何解此难题?

输入:

题目没有任何输入。

输出:

题目可能有种解决方法,求出步骤最少的解决方法,
按顺序输出农夫想把羊、菜、狼全部运过河需要哪几个步骤。
如果需要将羊带过河去则输出“sheep_go”。
如果需要将羊带回来则输出“sheep_come”。
如果需要将菜带过河去则输出“vegetable_go”。
如果需要将菜带回来则输出“vegetable_come”。
如果需要将狼带过河去则输出“wolf_go”。
如果需要将狼带回来则输出“wolf_come”。
如果需要空手返回则输出“nothing_come”。
如果需要空手过河则输出“nothing_go”。
每输出一种方案,输出一行“succeed”。

样例输入:

样例输出:

提示:

题目可能有多组解决方法,每种方法输出后要再空一行。
一种方法中的多句话,每句话占一行。


java 代码如下:
public class Main {

	public static void main(String[] args) {
		System.out.println("sheep_go");
		System.out.println("nothing_come");
		System.out.println("vegetable_go");
		System.out.println("sheep_come");
		System.out.println("wolf_go");
		System.out.println("nothing_come");
		System.out.println("sheep_go");
//		System.out.println();

	}

}
/**************************************************************
	Problem: 1204
	User: coder
	Language: Java
	Result: Accepted
	Time:60 ms
	Memory:14576 kb
****************************************************************/


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false