首页 > 代码库 > 广度优先(迷宫找人)
广度优先(迷宫找人)
1 import java.util.LinkedList; 2 3 public class One { 4 public static void main(String args[]){ 5 int n,m,p,q;//n,m为数组实际迷宫的行列,p,q为目标地的数组行纵号 6 int a[][]=new int[51][51],book[][]=new int[51][51];//迷宫和标记数组 7 int d[][]={{0,1},{1,0},{0,-1},{-1,0}};//方向数组,用于遍历各个方向 8 Scanner scanner=new Scanner(System.in); 9 System.out.println("请输入迷宫行列数:"); 10 n=scanner.nextInt(); 11 m=scanner.nextInt(); 12 System.out.println("输入迷宫:"); 13 for(int i=1;i<=n;i++){ 14 for(int j=1;j<=m;j++){ 15 a[i][j]=scanner.nextInt(); 16 } 17 System.out.println(""); 18 } 19 System.out.println("请输入目的地数组坐标:"); 20 p=scanner.nextInt(); 21 q=scanner.nextInt(); 22 LinkedList<Note> list=new LinkedList<Note>(); 23 //初始化链表第一个点 24 list.add(new Note(1,1,0)); 25 book[1][1]=1; 26 int tx,ty,flag=0;//tx,ty用于表示扩展的数组行列号,flag用于表示是否找到了目的点 27 while(!list.isEmpty()){ 28 for(int k=0;k<=3;k++){//链表第一个点的扩展(四个方向) 29 tx=list.getFirst().x+d[k][0]; 30 ty=list.getFirst().y+d[k][1]; 31 //判断是否出界,或者有障碍,或者已经走过了 32 if(tx<1||ty<1||tx>n||ty>m||a[tx][ty]==1||book[tx][ty]==1)continue; 33 list.add(new Note(tx,ty,list.getFirst().step+1));//若没有过界,也没有障碍物,则把该扩展点加入到链表后面 34 if(tx==p&&ty==q){//若该扩展点为目的地,则flag=1表示找到了目的地,并且停止继续查找 35 flag=1; 36 break; 37 } 38 } 39 if(flag==1)break;//若找到了目的地,停止扩展 40 list.removeFirst(); 41 } 42 System.out.println(list.getLast().step); 43 } 44 } 45 class Note{ 46 int x,y,step; 47 Note(int x,int y,int step){ 48 this.x=x; 49 this.y=y; 50 this.step=step; 51 } 52 }
广度优先(迷宫找人)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。