递归问题:一穿越迷宫-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

递归问题:一穿越迷宫

简介:

迷宫问题的解决涉及到大量的试探和失败:选择一条路径,在无法前景时折回,并选择其他还未尝试过的路径。使用递归能够很好的处理这类问题。


package com.chingcloud.test01;


public class Maze {
private final int TRIED = 3 ;
private final int PATH = 7 ;
private int[][] grid = {{1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1}} ;

public boolean traverse(int row,int column){
boolean done = false ;
if(valid(row,column)){
grid[row][column] = TRIED ;
if(row == grid.length-1 && column == grid[0].length-1){
done = true ;
}else{
done = traverse(row+1,column) ;
if(!done){
done = traverse(row,column+1) ;
}
if(!done){
done = traverse(row-1,column) ;
}
if(!done){
done = traverse(row,column-1) ;
}
}
if(done){
grid[row][column] = PATH ;
}
}
return done ;
}
public boolean valid(int row,int column){
boolean result = false ;
if(row>=0 && row<grid.length && column>=0 && column<grid[row].length){
if(grid[row][column]==1){
result = true ;
}
}
return result ;
}
public String toString(){
String result = "\n" ;
for(int row=0;row<grid.length;row++){
for(int column=0;column<grid[row].length;column++){
result += grid[row][column] + "" ;
}
result += "\n" ;
}
return result ;
}
public static void main(String[] args) {
Maze labyrinth = new Maze() ;
System.out.println(labyrinth);
if(labyrinth.traverse(0,0)){
System.out.println("The maze was successfully traversed!");
}else{
System.out.println("There is no possible path.");
}
System.out.println(labyrinth);
}
}


result



1110110001111
1011101111001
0000101010100
1110111010111
1010000111001
1011111101111
1000000000000
1111111111111


The maze was successfully traversed!


7770110001111
3077707771001
0000707070300
7770777070333
7070000773003
7077777703333
7000000000000
7777777777777

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章