Difference between revisions of "TADM2E 8.17"
From Algorithm Wiki
(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
}