I am trying to find the shortest path through a map represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The the entrance is at the top left (0, 0) and the exit is at the bottom right (width - 1, height - 1).
My function solution(int[][] map) finds the length of the shortest path from the entrance to the exit, where you are allowed to remove one wall as part of the path. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. Conditions on map include that the starting and ending positions are always passable (0), the map will always be solvable, though you may or may not need to remove a wall, and that the height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.
A couple test cases:
Input:
int[][] a = {{0, 1, 1, 0},
{0, 0, 0, 1},
{1, 1, 0, 0},
{1, 1, 1, 0},
{1, 1, 1, 0}};
Output:
8
Input:
int[][] b = {{0, 1, 0, 0, 0},
{0, 0, 0, 1, 0},
{0, 0, 1, 1, 0},
{0, 1, 1, 0, 0},
{0, 1, 1, 0, 0}};
Output:
9
Input:
int[][] c = {{0, 1, 0, 0, 0},
{0, 0, 0, 1, 0},
{0, 0, 1, 1, 1},
{0, 1, 1, 0, 0},
{0, 1, 1, 0, 0}};
Output:
11
My code for my solution is as follows:
public static int solution(int[][] map) {
int rows = map.length;
int cols = map[0].length;
Graph graph = new Graph(map);
Queue<Node> queue = new LinkedList<>();
ArrayList<Node> marked = new ArrayList<>();
Node start = graph.getNode(0, 0);
queue.add(start);
marked.add(start);
start.setDistanceFromStart(1);
while(!queue.isEmpty()) {
Node current = queue.remove();
if(current.getX() == rows - 1 && current.getY() == cols - 1) { //if we have reached goal node
return current.getDistanceFromStart();
}
for(Node n : current.getNeighbors()) {
queue.add(n);
n.setDistanceFromStart(current.getDistanceFromStart() + 1);
}
}
return -1; //no path found
}
I created two classes with the along with the solution method, Graph and Node:
class Graph{
private Node[][] _nodeMap;
private int _rows;
private int _cols;
public Graph(int[][] map) {
_nodeMap = new Node[map.length][map[0].length];
_rows = _nodeMap.length;
_cols = _nodeMap[0].length;
for (int i = 0; i < _rows; i++) {
for(int j = 0; j < _cols; j++) {
_nodeMap[i][j] = new Node(i, j, map[i][j], false, this);
}
}
}
/**
* Gets the Node at location (x,y)
* @param x - the x val of the Node being retrieved
* @param y - the y val of the Node being retrieved
* @return
*/
public Node getNode(int x, int y) {
return _nodeMap[x][y];
}
/**
* Replace the node at x,y with the new node n.
* @param x
* @param y
* @param n
*/
public void setNode(int x, int y, Node n) {
_nodeMap[x][y] = n;
}
/**
* Checks to see if a node has a neighbor (either a wall or a path) to the north
* @param n - the node being checked
* @return boolean - true if there is a neighbor, false if there is not
*/
public boolean hasNorth(Node n) {
if(n.getX() > 0) {
return true;
} else {
return false;
}
}
/**
* Return's the neighbor to the north
* @param n - the current node
* @return Returns the Node to the north of n
*/
public Node getNorth(Node n) {
return _nodeMap[n.getX() - 1][n.getY()];
}
/**
* Checks to see if a node has a neighbor (either a wall or a path) to the south
* @param n - the node being checked
* @return boolean - true if there is a neighbor, false if there is not
*/
public boolean hasSouth(Node n) {
if(n.getX() < _rows - 1) {
return true;
} else {
return false;
}
}
/**
* Return's the neighbor to the south
* @param n - the current node
* @return Returns the Node to the south of n
*/
public Node getSouth(Node n) {
return _nodeMap[n.getX() + 1][n.getY()];
}
/**
* Checks to see if a node has a neighbor (either a wall or a path) to the east
* @param n - the node being checked
* @return boolean - true if there is a neighbor, false if there is not
*/
public boolean hasEast(Node n) {
if(n.getY() < _cols - 1) {
return true;
} else {
return false;
}
}
/**
* Return's the neighbor to the east
* @param n - the current node
* @return Returns the Node to the east of n
*/
public Node getEast(Node n) {
return _nodeMap[n.getX()][n.getY() + 1];
}
/**
* Checks to see if a node has a neighbor (either a wall or a path) to the west
* @param n - the node being checked
* @return boolean - true if there is a neighbor, false if there is not
*/
public boolean hasWest(Node n) {
if(n.getY() > 0) {
return true;
} else {
return false;
}
}
/**
* Return's the neighbor to the west
* @param n - the current node
* @return Returns the Node to the west of n
*/
public Node getWest(Node n) {
return _nodeMap[n.getX()][n.getY() - 1];
}
}
class Node {
private int _x; //x location
private int _y; //y location
private int _type; //1 if a wall, 0 if a path
private Graph _map;
private int _distFromStart;
private boolean _wallRemoved;
public Node(int x, int y, int type, boolean wallRemoved, Graph map){
_x = x;
_y = y;
_type = type;
_wallRemoved = wallRemoved;
_map = map;
_distFromStart = -1;
}
public int getX() {
return _x;
}
public int getY() {
return _y;
}
public int getType() {
return _type;
}
public boolean getWallRemoved() {
return _wallRemoved;
}
public int getDistanceFromStart() {
return _distFromStart;
}
public void setDistanceFromStart(int distance) {
_distFromStart = distance;
}
/**
* Returns an ArrayList<Node> containing the neighbors of a node.
* @return
*/
public ArrayList<Node> getNeighbors(){
ArrayList<Node> neighbors = new ArrayList<>();
if(this._wallRemoved) { //if a wall has already been removed
if(_map.hasWest(this) && _map.getWest(this)._type == 0) { //check west neighbor
Node node = _map.getWest(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map/*, node._timesEvaluated + 1*/);
neighbors.add(n);
}
if(_map.hasEast(this) && _map.getEast(this)._type == 0) { //check east neighbor
Node node = _map.getEast(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
neighbors.add(n);
}
if(_map.hasNorth(this) && _map.getNorth(this)._type == 0) { //check north neighbor
Node node = _map.getNorth(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
neighbors.add(n);
}
if(_map.hasSouth(this) && _map.getSouth(this)._type == 0) { //check south neighbor
Node node = _map.getSouth(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map/);
neighbors.add(n);
}
} else { //if a wall hasn't been removed yet
if(_map.hasWest(this)) { //check west neighbor
if(_map.getWest(this)._type == 1) { //if west neighbor is a wall
if(!this._wallRemoved) {
Node node = _map.getWest(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
neighbors.add(n);
}
} else { //if west neighbor is a path
Node node = _map.getWest(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), false, _map);
neighbors.add(n);
}
}
if(_map.hasEast(this)) { //check east neighbor
if(_map.getEast(this)._type == 1) {
if(!this._wallRemoved) {
Node node = _map.getEast(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
neighbors.add(n);
}
} else {
Node node = _map.getEast(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), false, _map);
neighbors.add(n);
}
}
if(_map.hasNorth(this)) { //check north neighbor
if(_map.getNorth(this)._type == 1) {
if(!this._wallRemoved) {
Node node = _map.getNorth(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
neighbors.add(n);
}
} else {
Node node = _map.getNorth(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), false, _map);
neighbors.add(n);
}
}
if(_map.hasSouth(this)) { //check south neighbor
if(_map.getSouth(this)._type == 1) {
if(!this._wallRemoved) {
Node node = _map.getSouth(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), true, _map);
neighbors.add(n);
}
} else {
Node node = _map.getSouth(this);
Node n = new Node(node.getX(), node.getY(), node.getType(), false, _map);
neighbors.add(n);
}
}
}
return neighbors;
}
}
My code works, the correct answer is returned for each test case. My issue is that the code is terribly slow. I'm pretty sure that the maze is being solved by brute force (if not, the time constraint is at least similar to brute force) causing large maps (such as a 20x20 map) to take a very long time to solve. How can this I optimize my code to make it run more quickly? Thanks!
You have this ArrayList called "marked". I would suggest to use it ;)
for(Node n : current.getNeighbors()) {
if(!marked.contains(n)){
queue.add(n);
n.setDistanceFromStart(current.getDistanceFromStart() + 1);
marked.add(n);
}
}
This reduces the complexity to O(n * m), where n,m are the dimensions of the grid.
Also read about BFS algoritm in 2d space. Good luck :)
EDIT #1
If you would like to improve the code more then that try to check A* algorithm.
Also instead of the Queue you can keep all "in progress" nodes on PriorityQueue with special parameter which will try to choose the best node. This parameter can be the distance in cartesian plane between the node and (width - 1, height - 1) (simple Pythagoras' Theorem). Good Luck again :)