Tcaner: Added solution to one of the problems.

2019-12-25T01:50:02Z

Added solution to one of the problems.

New page

[[TADM2E 8.17|(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;
}

Talk:Divide-TADM2E - Revision history

Tcaner: Added solution to one of the problems.