Difference between revisions of "TADM2E 8.17"

From Algorithm Wiki
Jump to: navigation, search
(Created page with "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, RR...")
 
(Added the solution in Java, with different implementation details.)
Line 103: Line 103:
 
   
 
   
 
  print $np, "\n";
 
  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
 +
}

Revision as of 01:46, 25 December 2019

Consider the following example:

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:

1 ? ? ?
? B ? ?
? ? ? ?


1 1 ? ?
1 B ? ?
? ? ? ?


1 1 1 ?
1 B ? ?
1 ? ? ?


1 1 1 1
1 B 1 ?
1 1 ? ?


1 1 1 1
1 B 1 2
1 1 2 ?


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

}