View source for TADM2E 8.17

Consider the following example:

{|border="1"
|G||G||G||G
|-
|G||B||G||G
|-
|G||G||G||G
|}

There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD.  We can start at the top-left and fill each square with the possible number of routes that lead to it:

{|border="1"
|1||?||?||?
|-
|?||B||?||?
|-
|?||?||?||?
|}


{|border="1"
|1||1||?||?
|-
|1||B||?||?
|-
|?||?||?||?
|}


{|border="1"
|1||1||1||?
|-
|1||B||?||?
|-
|1||?||?||?
|}


{|border="1"
|1||1||1||1
|-
|1||B||1||?
|-
|1||1||?||?
|}


{|border="1"
|1||1||1||1
|-
|1||B||1||2
|-
|1||1||2||?
|}


{|border="1"
|1||1||1||1
|-
|1||B||1||2
|-
|1||1||2||4
|}

Implementation in Perl:

 #!/usr/bin/perl
 
 use warnings;
 use strict;
 
 sub count_paths
   {
   my @bad = @_;
 
   my $nr = @bad;
   my $nc = @{$bad[0]};
 
   my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;
 
   for my $r (0 .. $nr - 1)
     {
     for my $c (0 .. $nc - 1)
       {
       next if $bad[$r][$c];
 
       my $np = $r == 0 && $c == 0 ? 1 : 0;
 
       $np += $paths[$r - 1][$c]     if $r > 0 && !$bad[$r - 1][$c];
       $np += $paths[$r]    [$c - 1] if $c > 0 && !$bad[$r]    [$c - 1];
 
       $paths[$r][$c] = $np;
       }
     }
 
   return $paths[$nr - 1][$nc - 1];
   }
 
 my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0]);
 
 my $np = count_paths @bad;
 
 print $np, "\n";


The solution in Java, different example:

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; // can't be solution
        }
        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; // wrong solution
}