疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java实现的非递归方法迷宫搜索


 

   

  1 import java.util.Scanner;

  2 import java.util.Stack;

  3 class Point

  4 {

  5 int x;

  6 int y;

  7 public Point(int x,int y)

  8 {

  9 this.x = x;

  10 this.y = y;

  11 }

  12 }

  13

  14 public class MazeFindPath

  15 {

  16

  17 public static void main(String[] args){

  18 int[][] map;

  19 Stack mazestack;

  20 Point curpos;

  21 Scanner in = new Scanner(System.in);

  22 while(in.hasNextInt()){

  23 int row = in.nextInt();

  24 int col = in.nextInt();

  25

  26 mazestack = new Stack ();

  27 map = new int[row][col];

  28 curpos = new Point(0,0);

  29

  30

  31

  32 //生成迷宫数组

  33 int i,j;

  34 for(i=0;i

  35 for(j=0;j

  36 map[i][j] = in.nextInt();

  37 }

  38 }

  39

  40 //从起点开始进行搜索

  41 do{

  42 if(map[curpos.x][curpos.y]==0){//如果当前位置可通

  43 //把当前位置压入栈中;

  44 mazestack.push(curpos);

  45 //把当前位置标记为已经过,不可通过

  46 if(curpos.x==col-1&&curpos.y==col-1){//如果当前位置为终点,则结束算法。

  返回栈中存储的路径

  47 break;

  48 }

  49 map[curpos.x][curpos.y]=1;

  50 //依次从上下左右四个方向进行搜索

  51 if(curpos.y-1>=0&&map[curpos.x][curpos.y-1]==0){

  52 curpos = new Point(curpos.x,curpos.y-1);

  53 }//向上搜索

  54 else if(curpos.x+1

  55 curpos = new Point(curpos.x+1,curpos.y);

  56 }//向右搜索

  57 else if(curpos.y+1

  58 curpos = new Point(curpos.x,curpos.y+1);

  59 }//向下搜索

  60 else if(curpos.x-1>=0&&map[curpos.x-1][curpos.y]==0){

  61 curpos = new Point(curpos.x-1,curpos.y);

  62 }//向左搜索

  63 else{//四个方向都不可通过

  64 continue;

  65 }

  66

  67 }//当前位置可以通过算法的结束

  68 else {//当前位置不可通过

  69 if(!mazestack.empty()){//如果栈不为空,弹栈

  70 mazestack.pop();//这次弹栈的是四个方向都已经是不可以通过的位置

  71 }

  72 Point top =mazestack.peek();

  73 map[top.x][top.y]=0;//先恢复栈顶元素位置为可以通过,

  74 //因为下次对当前位置进行判断时需要可以通过进行搜索

  75 curpos=new Point(top.x,top.y);

  76 mazestack.pop();//弹出恢复之前的那个位置,因为之后还要把他压入栈一次。

  77 }

  78 }

  79 while(!mazestack.empty()&&!(curpos.x==col-1&&curpos.y==row-1));

  80 //当栈不为空或者当前位置不为出口位置时,继续搜索下去

  81 if(mazestack.empty()){//当栈为空时,表示没有这样的路径

  82 System.out.println("there is no such a way from these two points!");

  83 }

  84

  85 else{//找到一条这样的路径。

  86 Stack stackout = new Stack ();

  87 while(!mazestack.empty()){

  88 Point temp = mazestack.peek();

  89 stackout.push(temp);

  90 mazestack.pop();

  91 }

  92 while(!stackout.empty()){

  93 Point temp = stackout.peek();

  94 System.out.println("(" + temp.x+","+temp.y+ ")");

  95 stackout.pop();

  96 }

  97 }

  98 }

  99 }

  100 }

  101 /*

  102 迷宫

  103 6 6

  104 0 1 1 1 1 1

  105 0 0 1 1 1 0

  106 0 0 0 0 1 0

  107 1 0 0 1 1 1

  108 1 1 0 0 0 1

  109 1 1 0 1 0 0

  110 */