基础测试的农夫过河问题

舍我其谁

花了好多天学习java基础，刚刚才提交了基础测试题，觉得最后一道题挺有意思的，第十题：一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。编程解决猫狗鱼过河问题。有木有同学和我一样的题目，可以一起讨论一下。
想了好久，最后用图论深度优先搜索解决。
思路：假设刚开始渡河的那边人、猫、鱼、狗各个状态是（用二进制表示）：0000，那么成功过河后他们的各个状态是：1111。所以过河问题就是从0000起始状态到1111最终状态的过程，因此总共有16中状态。然后把每一种状态看成图的一个结点，把可以连通的结点用有向边连起来，就构成的一个有向图。从0000这个结点遍历（深度优先搜索）图，遍历到1111结点则找到解。
附上代码，仅供参考，可能有错误，望大神指正：

public class Test10 {
private int[][] maxtri = new int[16][16]; // 邻接矩阵，存储结点是否联通
private int[][] flag = { { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 },
{ 5, 0 }, { 6, 0 }, { 7, 0 }, { 8, 0 }, { 9, 0 }, { 10, 0 },
{ 11, 0 }, { 12, 0 }, { 13, 0 }, { 14, 0 }, { 15, 0 } };// 状态是否被访问过的数组
private Stack stack = new Stack();
/**
* 得到状态的字符串表示 0000 四位分别代表人猫鱼狗
* @param x 状态值
* @return 格式化的字符串
*/
public String getFormatString(int x) {
String X = Integer.toBinaryString(x);
if (X.length() < 4 && X.length() >= 3) {
X = "0" + X;
} else if (X.length() < 3 && X.length() >= 2) {
X = "00" + X;
} else if (X.length() < 2 && X.length() >= 1) {
X = "000" + X;
}
return X;
}
/**
* 判断两个结点是否连通
* @param x 前一个结点状态
* @param y 后一个结点状态
* @return 连通为1 ，不连通为0
*/
private boolean isConnected(int x, int y) {
String X = getFormatString(x);
String Y = getFormatString(y);
if (X.charAt(0) == Y.charAt(0))
return false;
else {
if (X.charAt(1) != Y.charAt(1) && X.charAt(2) != Y.charAt(2)
&& X.charAt(3) != Y.charAt(3)) {
return false;
}
else if (X.charAt(1) != Y.charAt(1) && X.charAt(2) != Y.charAt(2)) {
return false;
}
else if (X.charAt(1) != Y.charAt(1) && X.charAt(3) != Y.charAt(3)) {
return false;
}
else if (X.charAt(2) != Y.charAt(2) && X.charAt(3) != Y.charAt(3)) {
return false;
}
else if (((X.charAt(0) != X.charAt(1)) && (X.charAt(1) != Y.charAt(1)))
|| ((X.charAt(0) != X.charAt(2)) && (X.charAt(2) != Y.charAt(2)))
|| ((X.charAt(0) != X.charAt(3)) && (X.charAt(3) != Y.charAt(3)))) {
return false;
}
return true;
}
}
/**
* 初始化邻接矩阵
*/
public void InitMaxtri(){
for (int i = 0; i <16; i++) {
for (int j = 0; j < 16; j++) {
if(isConnected(i, j)){
maxtri[i][j] = 1;
}
else{
maxtri[i][j] = 0;
}
}
}
}
/**
* 得到与输入节点相连的一个结点
* @param x
* @return
*/
public int getVetex(int x){
for (int i = 0; i < 16; i++) {
if(maxtri[x][i] == 1 && flag[i][1] == 0){
String X = getFormatString(i);
if((X.charAt(0)!=X.charAt(1)&&X.charAt(1)==X.charAt(3))||
(X.charAt(0)!=X.charAt(1)&&X.charAt(1)==X.charAt(2))){
continue;
}
else {
return i;
}
}
}
return -1;
}
/**
* 深度优先搜索
*/
public void DFS(){
stack.push(0);
flag[0][1]=1;
while(!stack.isEmpty()){
if(stack.getTop() == 15){
break;
}
int Vetex = getVetex(stack.getTop());
if(Vetex==-1){
try{
stack.pop();
}catch(Exception e){
e.printStackTrace();
}
}
else{
stack.push(Vetex);
flag[Vetex][1] = 1;
}
}
}
/**
* 打印结果
* @throws Exception
*/
public void printOrder() throws Exception{
for(int i=0;i< stack.getLength()-1;i++){
int x=stack.seekByIndex(i);
int y=stack.seekByIndex(i+1);
String X=getFormatString(x);
String Y=getFormatString(y);
String type="";
if(X.charAt(0)=='0'){
type="过河";
}
if(X.charAt(0)=='1'){
type="回来";
}
if(X.charAt(1)!=Y.charAt(1)){
System.out.println("人带猫"+type);
}
else if(X.charAt(2)!=Y.charAt(2)){
System.out.println("人带鱼"+type);
}
else if(X.charAt(3)!=Y.charAt(3)){
System.out.println("人带狗"+type);
}
else{
System.out.println("人自己"+type);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Test10 test = new Test10();
test.InitMaxtri();
test.DFS();
try{
test.printOrder();
}catch(Exception e){
e.printStackTrace();
}
}
/**
* 数据栈
* @author daoqin
*/
public class Stack{
private int[] num;
private int top;
public Stack(){
InitStack();
}
public void InitStack(){
top = -1;
num = new int[16];
}
public int getTop(){
return num[top];
}
public int pop() throws Exception{
if(top>=0){
return num[top--];
}
else{
throw new Exception("栈空");
}
}
public void push(int x){
num[++top]=x;
}
public boolean isEmpty(){
return (top<0);
}
public int getLength(){
return top+1;
}
public int seekByIndex(int index)throws Exception{
if(index < getLength() && index >= 0){
return num[index];
}
else {
throw new Exception("未找到元素！");
}
}
}
}

复制代码

lostyou · lostyou

学习了,这个想法真的很6

okandy520 · okandy520

很少回帖，切实的赞一个，方法很好。Q553403028，有时间可以交流下，我算法可能比不上你。呵呵

夕默 · 夕默

哇塞！楼主学过数据结构吗？我也学过，但是我这是第一次见到将图运用起来的例子！赞一个！

daoqin · daoqin

残羹夜宴丶发表于 2014-10-3 08:39
楼主的思维也比较神奇，这么复杂的代码，竟然给写出来了。

亲，这个题目不难，代码不复杂的！别人用的回溯才复杂！

残羹夜宴丶 · 残羹夜宴丶

楼主的思维也比较神奇，这么复杂的代码，竟然给写出来了。

小城。 · 小城。

楼主的基础测试这么难。。

weiyi · weiyi

好复杂啊

daoqin · daoqin

发现大家习惯了用集合做各种题目，有时候效率很重要，集合写起来虽简单，却容易误导我们的思维！

备战 · 备战

好难呀，，这是神马。。

谢建平 · 谢建平

没学过这些算法很头痛啊

clh · clh

基础测试这么难啊

daoqin · daoqin

恩，同学，你接触过图论吗？没有的话可以去看看，真心觉得挺有用的

Fightin黑马 · Fightin黑马

daoqin 发表于 2014-9-10 21:57
感觉用集合来做判断条件太多，因为这个状态太多了，不容易操作，当然集合做也挺好的。 ...

用集合做的话最起码代码阅读性要高一点,矩阵的话我反正看的挺晕的

daoqin · daoqin

Fightin黑马发表于 2014-9-10 21:30
为什么不用集合做呢,不过你用矩阵确实是一个很新颖的想法哦

感觉用集合来做判断条件太多，因为这个状态太多了，不容易操作，当然集合做也挺好的。

Fightin黑马 · Fightin黑马

daoqin 发表于 2014-9-10 21:25
从何说起啊？

为什么不用集合做呢,不过你用矩阵确实是一个很新颖的想法哦

huanglyhf · huanglyhf

代码我还没看，光前面把这16种状态想成二进制的主意就要赞一个！

daoqin · daoqin

Fightin黑马发表于 2014-9-10 20:42
好复杂的说

从何说起啊？

Fightin黑马 · Fightin黑马

好复杂的说

帐号		自动登录	找回密码
密码			加入黑马

基础测试的农夫过河问题

评分

18 个回复

浏览过的版块

黑马骑士勋章