定义一个二维数组:
intmaze[5][5]={
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
输入二维数组:
5 5
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
输出:
路径: [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [4, 4]]
共用步数 9
va">class Mnode{
int x;
int y;
int deeps=1;
List list=new ArrayList();
public Mnode(int x, int y) {
this.x = x;
this.y = y;
}
}
public class MiGong {
public static void main(String[] args) {
//初始化地图
Scanner scanner=new Scanner(System.in);
int a[][]=new int[5][5];
for (int i = 0; i <a.length ; i++) {
String temp[]=scanner.next().split(",");
for (int j = 0; j <a[i].length ; j++) {
a[i][j]= Integer.parseInt(temp[j]);
}
}
//进行选路
int x=sumit(a);
if (x==0){
System.out.println("无法走出");
}
else System.out.println("共用步数 "+x);
}
public static int sumit(int[][] a){
int deeps=0; //当前节点深度
//记录当前节点是否被访问过
boolean[][] is=new boolean[a.length][a[0].length];
for (int i = 0; i <a.length ; i++) {
for (int j = 0; j <a[i].length ; j++) {
is[i][j]=true;
}
}
int way[][]={{0,1},{1,0},{0,-1},{-1,0}}; //下个节点四个方向
//初始节点
Mnode mnode=new Mnode(0,0);
List il=new ArrayList();
il.add(0);
il.add(0);
mnode.list.add(il);
is[0][0]=false;
//初始节点加入队列
Queue<Mnode> queue=new LinkedList();
queue.add(mnode);
//
while (!queue.isEmpty()){
Mnode mnode1=queue.poll();
deeps=mnode1.deeps;
//到达终点返回
if (mnode1.x==a[0].length-1&&mnode1.y==a.length-1){
System.out.println("路径: "+mnode1.list);
return deeps;
}
//遍历该点周围节点
for (int i = 0; i <4 ; i++) {
int x=mnode1.x+way[i][0];
int y=mnode1.y+way[i][1];
Mnode temp=new Mnode(x,y);
temp.deeps=mnode1.deeps+1;
//得到之前路径
for (int j = 0; j <mnode1.list.size() ; j++) {
temp.list.add(mnode1.list.get(j));
}
//添加该点进入所走路径
List list=new ArrayList();
list.add(temp.x);
list.add(temp.y);
temp.list.add(list);
//判断是否选取该点
if (isvalued(x,y)&&isway(a[x][y])&&is[x][y]){
is[x][y]=false;
queue.add(temp);
}
}
}
return 0;
}
//检查是否超过边界
public static boolean isvalued(int x,int y){
if (x>=5||y>=5||x<0||y<0) return false;
else return true;
}
//检查是否是路
public static boolean isway(int a){
if (a==1){
return false;
}
else return true;
}
}