Problem
You are given an HxW matrix. Each element is either 0 (passable space) or 1 (wall). Given that you can remove one wall, find the shortest path from [0,0] (start) to [width-1, height-1] (end).
Test cases
Inputs:
int[][] case 1 = { {0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}, {1, 1, 1, 0}, };Outputs:
7Inputs:
int[][] case2 = { {0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}, }Outputs:
11
Note, this is one of the google foobar challenges. There are quite a few algorithms out there for this problem. However, I'm trying to solve this using a variation of A*. My problem is that currently, my algorithms works like this:
- Get all wall locations.
- For each wall:
- Construct maze without the wall.
- Use A* to find the shortest path.
- Return the min of the found shortest paths.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;
class Cell {
// Normal Cell things..
int x,y;
boolean isWall;
// A* shenanigans (should probably be decoupled).
int localScore; // The distance from the start.
int globalScore; // The distance from the end (heuristic).
boolean isVisited;
// What I tried is to include a `canRemove` boolean here to indicate whether we can still remove walls within this point.
Cell(int x, int y, boolean isWall) {
this.x = x;
this.y = y;
this.isWall = isWall;
this.localScore = Integer.MAX_VALUE;
this.globalScore = Integer.MAX_VALUE;
}
// Copy constructor.
Cell(Cell anotherCell) {
this.x = anotherCell.x;
this.y = anotherCell.y;
this.isWall = anotherCell.isWall;
this.isVisited = anotherCell.isVisited;
this.localScore = anotherCell.localScore;
this.globalScore = anotherCell.globalScore;
}
}
class Station {
Cell[][] cells;
List<Cell> walls;
int height, width;
Station(int[][] rawStation) {
// Create Maze
this.height = rawStation.length;
this.width = rawStation[0].length;
this.cells = new Cell[height][width];
walls = new ArrayList<>();
for(int y=0; y<height; y++){
for(int x=0; x<width; x++){
Cell cell = new Cell(x, y, rawStation[y][x] == 1);
this.cells[y][x] = cell;
if(cell.isWall) walls.add(cell);
}
}
}
Station(Station station) {
this.height = station.height;
this.width = station.width;
this.cells = new Cell[height][width];
this.walls = new ArrayList<>();
for(int y=0; y<height; y++){
for(int x=0; x<width; x++){
cells[y][x] = new Cell(station.cells[y][x]);
}
}
}
Cell start() {
return cells[0][0];
}
Cell end() {
return cells[height-1][width-1];
}
Optional<Cell> getCell(int x, int y) {
if(x >= 0 && x < width && y >= 0 && y < height) {
return Optional.of(cells[y][x]);
}
return Optional.empty();
}
List<Cell> getCellNeighbours(Cell cell) {
List<Optional<Cell>> neighbours = new ArrayList<>();
neighbours.add(getCell(cell.x, cell.y+1)); // TOP
neighbours.add(getCell(cell.x, cell.y-1)); // BOTTOM
neighbours.add(getCell(cell.x-1, cell.y)); // LEFT
neighbours.add(getCell(cell.x+1, cell.y)); // RIGHT
return neighbours.stream()
.filter(Optional::isPresent)
.map(Optional::get)
.collect(Collectors.toList());
}
}
class BunnySaver {
Station station;
List<Cell> discoveredCells;
boolean hasBomb;
BunnySaver(Station station) {
this.station = station;
this.discoveredCells = new ArrayList<>();
this.hasBomb = true;
}
int findShortestPath() {
Cell current = station.start();
current.localScore = 1;
current.isVisited = false;
current.globalScore = distance(current, station.end());
discoveredCells.add(station.start());
while(!discoveredCells.isEmpty() && current != station.end()) {
// Get the cell that has the lowest global score - aka lowest potential
// distance from end. Also remove it from the discovered list.
discoveredCells = discoveredCells.stream()
.sorted(Comparator.comparingInt(cell -> cell.globalScore))
.filter(cell -> !cell.isVisited)
.collect(Collectors.toList());
if(discoveredCells.isEmpty()) break;
current = discoveredCells.remove(0);
current.isVisited = true;
for(Cell neighbour : station.getCellNeighbours(current)) {
// If the neighbour is not already visited and it's not a wall,
// mark it as discovered.
if(neighbour.isVisited || neighbour.isWall)
continue;
discoveredCells.add(neighbour);
// If the neighbour's new localScore is lower than
// the old one => update the cell.
int possibleNeighbourLocalScore = current.localScore + distance(current, neighbour);
if(neighbour.localScore > possibleNeighbourLocalScore) {
neighbour.localScore = possibleNeighbourLocalScore;
neighbour.globalScore = neighbour.localScore + distance(neighbour, station.end());
}
}
}
if (current == station.end())
return current.localScore;
return Integer.MAX_VALUE;
}
// Manhattan distance used for A*.
int distance(Cell cell1, Cell cell2) {
int deltaX = Math.abs(cell1.x - cell2.x);
int deltaY = Math.abs(cell1.y - cell2.y);
return deltaX + deltaY;
}
}
public class Solution {
public static int solution(int[][] map) {
Station station = new Station(map);
int minPath = Integer.MAX_VALUE;
// Edge case: there are no walls.
if(station.walls.isEmpty()) {
BunnySaver saver = new BunnySaver(station);
return saver.findShortestPath();
}
// Remove check all possible wall removals.
for(Cell wall : station.walls) {
Station copy = new Station(station);
copy.cells[wall.y][wall.x].isWall = false;
BunnySaver saver = new BunnySaver(copy);
minPath = Math.min(minPath, saver.findShortestPath());
}
return minPath;
}
}
This as you can guess is very inefficient. What would be a good way of implementing the wall logic to be within the A* algorithm? I've tried to simply add a canRemove boolean to the Cell object (which is holding the state), however, that causes backtracking issues as diverged paths can alter the same state. I need to find a way of decoupling the state away from the Cell object and ultimately the A* algo.
