# Can someone help me with a test case ?

• I'm having trouble with the following input:

[[1,1,1,1,1,0],[0,0,0,0,0,1],[0,1,1,0,0,1],[1,0,0,1,0,1],[1,0,1,0,0,1],[1,0,0,0,0,1],[0,1,1,1,1,0]]

Shortest distance computed by my BFS code is 89, but Judge says its 88, for cell (4,4). I solved the example by hand, but I'm still seeing 89 (sum of all the red numbers in the picture below):

Here's my BFS code:

public class Solution {
public int shortestDistance(int[][] grid) {

``````    List<BFSLocation> houseLocations = getHouseLocations(grid);

boolean visited[][][] = new boolean[grid.length][grid[0].length][houseLocations.size()];

int[][] visitCount = new int[grid.length][grid[0].length];

int[][] distanceSum = new int[grid.length][grid[0].length];

for(BFSLocation loc: houseLocations) {
visited[loc.y][loc.x][loc.i] = true;
}

BFSLocation tmpLoc;
while(!queue.isEmpty()) {
tmpLoc = queue.poll();

if(tmpLoc.distanceFromBase > 0) {
visitCount[tmpLoc.y][tmpLoc.x]++;

distanceSum[tmpLoc.y][tmpLoc.x] += tmpLoc.distanceFromBase;

}

if(tmpLoc.distanceFromBase > 0 && visitCount[tmpLoc.y][tmpLoc.x] == houseLocations.size()) {

System.out.println("Row: " + tmpLoc.y + ", Col: " + tmpLoc.x);

return distanceSum[tmpLoc.y][tmpLoc.x];
} else {

if(tmpLoc.x > 0 && !visited[tmpLoc.y][tmpLoc.x - 1][tmpLoc.i] && grid[tmpLoc.y][tmpLoc.x - 1] == 0) {
visited[tmpLoc.y][tmpLoc.x - 1][tmpLoc.i] = true;
queue.add(new BFSLocation(tmpLoc.x - 1, tmpLoc.y, tmpLoc.i, tmpLoc.distanceFromBase + 1));
}

if(tmpLoc.x < grid[0].length-1 && !visited[tmpLoc.y][tmpLoc.x + 1][tmpLoc.i] && grid[tmpLoc.y][tmpLoc.x + 1] == 0) {
visited[tmpLoc.y][tmpLoc.x + 1][tmpLoc.i] = true;
queue.add(new BFSLocation(tmpLoc.x + 1, tmpLoc.y, tmpLoc.i, tmpLoc.distanceFromBase + 1));
}

if(tmpLoc.y > 0 && !visited[tmpLoc.y - 1][tmpLoc.x][tmpLoc.i] && grid[tmpLoc.y - 1][tmpLoc.x] == 0) {
visited[tmpLoc.y - 1][tmpLoc.x][tmpLoc.i] = true;
queue.add(new BFSLocation(tmpLoc.x, tmpLoc.y - 1, tmpLoc.i, tmpLoc.distanceFromBase + 1));
}

if(tmpLoc.y < grid.length-1 && !visited[tmpLoc.y + 1][tmpLoc.x][tmpLoc.i] && grid[tmpLoc.y + 1][tmpLoc.x] == 0) {
visited[tmpLoc.y + 1][tmpLoc.x][tmpLoc.i] = true;
queue.add(new BFSLocation(tmpLoc.x, tmpLoc.y + 1, tmpLoc.i, tmpLoc.distanceFromBase + 1));
}
}
}

return -1;
}

public List<BFSLocation> getHouseLocations(int[][] grid) {
List<BFSLocation> output = new ArrayList<BFSLocation>();

int count = 0;

for(int y=0; y<grid.length; y++) {
for(int x=0; x < grid[0].length; x++) {
if(grid[y][x] == 1) {
count++;
}
}
}

return output;
}
``````

}

class BFSLocation {
int x;
int y;
int i;
int distanceFromBase;

``````public BFSLocation(int ix, int iy, int ii, int d) {
x = ix;
y = iy;
i = ii;
distanceFromBase = d;
}
``````

}