import java.util.*; public class Main { public static void main(String[] args) { Scanner in =new Scanner(System.in); int[][] maze= new int[5][5]; int[][] room= new int[5][5]; for(int i =0;i<5;i++) { for(int j=0;j<5;j++) { maze[i][j]=in.nextInt(); } } ArrayList<int[]> step = new ArrayList<int[]>(); int[] start = {0,0}; step.add(start); step=findway(maze,room,0,0,step); for(int[] i :step) { System.out.println("("+i[0]+", "+i[1]+")"); } } public static ArrayList<int[]> findway(int[][] maze,int[][] room,int h ,int l,ArrayList<int[]> step) { room[h][l]=1; if(h==4 && l==4) { return (ArrayList<int[]>)step.clone(); }else { int min=Integer.MAX_VALUE; ArrayList<int[]> minstep = new ArrayList<int[]>(); int[][] next = {{-1,0},{1,0},{0,-1},{0,1}}; for(int[] i:next) { int nexth = h+i[0]; int nextl = l+i[1]; if(nexth>=0 && nexth<5 && nextl>=0 && nextl<5) { if(room[nexth][nextl]==0 && maze[nexth][nextl]==0) { room[nexth][nextl]=1; int[] a = {nexth,nextl}; step.add(a); ArrayList<int[]> newstep = findway(maze,room,nexth,nextl,step); room[nexth][nextl]=0; step.remove(a); if(min>newstep.size() && newstep.size()!=0 && newstep.get(newstep.size()-1)[0]==4 && newstep.get(newstep.size()-1)[1]==4) { min=newstep.size(); minstep=newstep; } } } } return minstep; } } } |
Double click to view unformatted code.