fork(4) download
copy 
  1. import java.util.*;
  2.  
  3. final class Coordinate {
  4.     private final int x;
  5.     private final int y;
  6.  
  7.     public Coordinate(int x, int y) {
  8.         this.x = x; 
  9.         this.y = y;
  10.     }
  11.  
  12.     public int getX() {
  13.         return x;
  14.     }
  15.  
  16.     public int getY() {
  17.         return y;
  18.     }
  19. }
  20.  
  21. class Maze {
  22.  
  23.     private final int[][] maze;
  24.  
  25.     public Maze(int[][] maze) {
  26.         if (maze == null) {
  27.             throw new NullPointerException("The input maze cannot be null");
  28.         }
  29.         if (maze.length == 0) {
  30.             throw new IllegalArgumentException("The size of maze should be greater than 0");
  31.         }
  32.  
  33.         this.maze = maze;
  34.     }
  35.  
  36.     public List<Coordinate> solve() {
  37.         return getMazePath(0, 0, new Stack<Coordinate>());
  38.     }
  39.  
  40.     private List<Coordinate> getMazePath(int row, int col, Stack<Coordinate> stack) {
  41.         assert stack != null;
  42.  
  43.         stack.add(new Coordinate(row, col));
  44.  
  45.         if ((row == maze.length - 1) && (col == maze[0].length - 1)) {
  46.             Coordinate[] coordinateArray = stack.toArray(new Coordinate[stack.size()]);
  47.             return Arrays.asList(coordinateArray);
  48.         }
  49.  
  50.         for (int j = col; j < maze[row].length; j++) {
  51.  
  52.             if ((j + 1) < maze[row].length && maze[row][j + 1] == 1) {
  53.                 return getMazePath(row, j + 1, stack);
  54.             }
  55.  
  56.             if ((row + 1) < maze.length && maze[row + 1][col] == 1) {
  57.                 return getMazePath(row + 1, col, stack);
  58.             }
  59.         }
  60.  
  61.         return Collections.emptyList();
  62.     }
  63.  
  64.  
  65.     public static void main(String[] args) {
  66.         int[][] m = {  {1, 1, 1},
  67.                        {1, 0, 1},
  68. 					   {1, 1, 0},                       
  69. 					   {0, 1, 1} };
  70.  
  71.         Maze maze = new Maze(m);
  72.  
  73.         for (Coordinate coord :  maze.solve()) {
  74.             System.out.println(coord.getX() + " : " + coord.getY());
  75.         }
  76.     }
  77. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cwlZI6
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!