Talk:Divide-TADM2E

(Solution 8.16)

Solution in Java:

public static void main(String[] args) {

       boolean[][] bad = {
               {false,true,false,false,false,true},
               {false,true,false,true,false,true},
               {false,true,false,true,false,true},
               {false,true,false,true,false,true},
               {false,true,false,true,false,true},
               {false,false,false,true,false,false},
       };
       boolean[][] visited = new boolean[bad.length][bad.length];
       int[][] cost = new int[bad.length][bad.length];
       for (int i = 0; i < cost.length; i++) {
           for (int j = 0; j < cost.length; j++) {
               cost[i][j] = Integer.MAX_VALUE;
           }
       }
       int result = shortestPath(bad,visited,cost);
       System.out.println(result);
   }

   private static class Point {
       int x, y;
       public Point(int x, int y) {
           this.x = x;
           this.y = y;
       }

       public Point toRight() {
           return new Point(x+1,y);
       }

       public Point toDown() {
           return new Point(x, y+1);
       }

       public Point toLeft() {
           return new Point(x-1,y);
       }

       public Point toUp() {
           return new Point(x,y-1);
       }
   }

public static int shortestPath(boolean[][] bad, boolean[][] visited, int[][] cost) {

       int length = bad.length;
       if (bad[0][0] || bad[length-1][length-1]) {
           return -1;
       }
       ArrayList<Point> queue = new ArrayList<>();
       queue.add(new Point(0,0));
       cost[0][0] = 0;
       Point next = null;
       while (!queue.isEmpty()) {
           next = queue.remove(0);
           if (next.x == length-1 && next.y == length-1) {
               return cost[next.x][next.y];
           }
           visited[next.x][next.y] = true;
           Point nextRight = next.toRight();
           if (canMoveRightFrom(next, length, bad)) {
               if (!visited(visited,nextRight,length)) {
                   queue.add(nextRight);
               }
               if (cost[nextRight.x][nextRight.y] > cost[next.x][next.y] + 1) {
                   cost[nextRight.x][nextRight.y] = cost[next.x][next.y] + 1;
               }
           }
           Point nextDown = next.toDown();
           if (canMoveDownFrom(next, length, bad)) {
               if (!visited(visited,nextDown,length)) {
                   queue.add(nextDown);
               }
               if (cost[nextDown.x][nextDown.y] > cost[next.x][next.y] + 1) {
                   cost[nextDown.x][nextDown.y] = cost[next.x][next.y] + 1;
               }
           }
           Point nextUp = next.toUp();
           if (canMoveUpFrom(next, length, bad)) {
               if (!visited(visited,nextUp,length)) {
                   queue.add(nextUp);
               }
               if (cost[nextUp.x][nextUp.y] > cost[next.x][next.y] + 1) {
                   cost[nextUp.x][nextUp.y] = cost[next.x][next.y] + 1;
               }
           }
           Point nextLeft = next.toLeft();
           if (canMoveLeftFrom(next, length, bad)) {
               if (!visited(visited,nextLeft,length)) {
                   queue.add(nextLeft);
               }
               if (cost[nextLeft.x][nextLeft.y] > cost[next.x][next.y] + 1) {
                   cost[nextLeft.x][nextLeft.y] = cost[next.x][next.y] + 1;
               }
           }
       }
       return -2;
   }