首页 > 代码库 > 百度真题之走迷宫
百度真题之走迷宫
题目：
给定一个矩阵，元素1表示可走路径，0表示不可走路径，从左上角开始，目标是值为9的坐标点，判断是否有一个路径到达目的地。如：
1 0 0 0 1 0
1 1 0 0 1 0
0 1 1 9 0 0
0 0 0 1 0 0
该矩阵存在到达数值为9的点的路径
分析：
这题和上一题城市规划的思路一致，只不过这里只要选取左上角第一个点即可。将已搜索的点放入到一个list。
代码：
package project001;import java.util.ArrayList;import java.util.List;public class Main14 { public static List<int[]> markedList = new ArrayList<int[]>();//存放已搜索的点 public static List<int[]> routeList = new ArrayList<int[]>();//存储路径，路径是由终点到起点 public static void main(String[] args) { int[][] maze = {{1,1,0,0,0}, {0,1,0,0,0}, {0,1,1,1,0}, {1,1,0,9,0}, {0,1,0,1,1}}; System.out.println(getRoute(fillM(maze))); printRoute(routeList); } public static boolean getRoute(int[][] M){ markPoint(1,1,M); //当routeList的大小大于1，说明存在路径到达目标 return routeList.size()>0; } public static int[][] fillM(int[][] M){ int row = M.length; int col = M[0].length; int[][] M2 = new int[row+2][col+2]; for(int i = 1;i<=row;i++){ for(int j=1;j<=col;j++){ M2[i][j]=M[i-1][j-1]; } } return M2; } //判断该点是否被标记 public static boolean isMarked(int i,int j){ int size = markedList.size(); if(size<=0) return false; for(int k=0;k<size;k++){ int[] m = markedList.get(k); if(m[0]==i&&m[1]==j) return true; } return false; } public static boolean markPoint(int i,int j,int[][] M){if(isMarked(i,j)) return false; //将该点标记，即放入一个list内 int[] m = new int[]{i,j}; markedList.add(m); if(M[i][j]==9) { routeList.add(m); return true; } //标记与点(i,j)相邻并且未被标记的点 if(!isMarked(i-1,j)&&M[i-1][j]>=1){ boolean res = markPoint(i-1,j,M); //当res为true，说明点(i,j)是正确路径点 if(res){ int[] m2 = new int[]{i-1,j-1};//之所以存放的点坐标为(i-1,j-1)，是因为当前矩阵是原来矩阵扩充后的，所以真实路径坐标比(i,j)要小1. routeList.add(m2); return true; } } if(!isMarked(i,j-1)&&M[i][j-1]>=1) { boolean res = markPoint(i,j-1,M); if(res){ int[] m2 = new int[]{i-1,j-1}; routeList.add(m2); return true; } } if(!isMarked(i,j+1)&&M[i][j+1]>=1){ boolean res = markPoint(i,j+1,M); if(res){ int[] m2 = new int[]{i-1,j-1}; routeList.add(m2); return true; } } if(!isMarked(i+1,j)&&M[i+1][j]>=1){ boolean res = markPoint(i+1,j,M); if(res){ int[] m2 = new int[]{i-1,j-1}; routeList.add(m2); return true; } } return false; } //打印矩阵 public static void printM(int[][] m){ int row = m.length; int col = m[0].length; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ System.out.print(m[i][j]+" "); } System.out.println(""); } } //打印坐标 public static void printRoute(List<int[]> list){ int size = list.size(); if(size<=0) return; for(int i=size-1;i>=0;i--){ int[] m =list.get(i); System.out.print("("+m[0]+","+m[1]+")-->"); } System.out.println(""); }}
百度真题之走迷宫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。