mementomori mementomori - 6 months ago 18
Java Question

Little changes in the given algorithm

It's about changing a maze algorithm.

What I mean by that? We got a 2-dimensional array filled with 0 and 1 where 0 stands for "not possible to pass" and 1 for "possible to pass".
An that algorithm finds its way from x to y (also known example: cat to mouse).
And this exactly is what the following algorithm is doing.

As input we got:

{1, 0, 0,},
{1, 1, 0},
{0, 1, 1} };


And the output:

(0,0) // ressembles the coordinates of the 1 in top left corner
(1,0) // ressembles the 1 under the first 1 I just explained
(1,1) // ...
(2,1)
(2,2)


I want change some little things:


  1. Change the starting and end position (this algorithm starts in top left and ends in bottom right) - I want mine to start in bottom left and end top right.

  2. This algorithm can only move down and right - I want only move up and right.



What changes need to be done, I'm pretty sure but I don't know how to code that:
For 1.) the problem seems to be:

public List<Coordinate> solve() {
return getMazePath(0, 0, new Stack<Coordinate>());
}


Somehow, I need to do 0-1 with the second zero but how if I haven't access to x and y declaration? I really believe 0-1 would make me start at bottom left instead of top left, is that right?

For 2.) changes for the column, also know as y need to be done.
Instead of +1 it requires -1, is that right?

Sorry for that wall of text, I really tried to keep it short but I seem to have failed :P
Anyway I hope someone will read this^^

Algorithm WITHOUT the changes:

import java.util.Arrays;
import java.util.*;

final class Coordinate {
private final int x;
private final int y;

public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}

public int getX() {
return x;
}

public int getY() {
return y;
}
}

public class Alg {

private final int[][] maze;

public Alg(int[][] maze) {
if (maze == null) {
throw new NullPointerException("The input maze cannot be null");
}
if (maze.length == 0) {
throw new IllegalArgumentException("The size of maze should be greater than 0");
}

this.maze = maze;
}

public List<Coordinate> solve() {
return getMazePath(0, 0, new Stack<Coordinate>());
}

private List<Coordinate> getMazePath(int row, int col, Stack<Coordinate> stack) {
assert stack != null;

stack.add(new Coordinate(row, col));

if ((row == maze.length - 1) && (col == maze[0].length - 1)) {
Coordinate[] coordinateArray = stack.toArray(new Coordinate[stack.size()]);
return Arrays.asList(coordinateArray);
}

for (int j = col; j < maze[row].length; j++) {

if ((j + 1) < maze[row].length && maze[row][j + 1] == 1) {
return getMazePath(row, j + 1, stack);
}

if ((row + 1) < maze.length && maze[row + 1][col] == 1) {
return getMazePath(row + 1, col, stack);
}
}

return Collections.emptyList();
}


public static void main(String[] args) {
int[][] m = { {1, 0, 0,},
{1, 1, 0},
{0, 1, 1} };

Alg maze = new Alg(m);

for (Coordinate coord : maze.solve()) {
System.out.println("("+coord.getX() + "," + coord.getY()+")");
}
}
}

Answer

Look at the method declaration for getMazePath. The current 0, 0 is passed as the row and col to that argument. So instead of sending 0, 0 to that method as currently coded, you'll send 2, 0 (for row 2, column 0, the bottom left).

The directional movements are in the for loop inside that getMazePath() method, the two if statements check if there is a 1 in column j + 1 (the column to the right) or in row row + 1 (the row below the current one). You'd modify those to use minus instead of plus to move to the left, or up, respectively.