Can someone help me with a test case ?


  • 0
    A

    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):

    alt text

    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];
        
        
        Queue<BFSLocation> queue = new LinkedList<BFSLocation>();
        
        for(BFSLocation loc: houseLocations) {
            queue.add(loc);
            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) {
                    output.add(new BFSLocation(x, y, count, 0));
                    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;
    }
    

    }


  • 0
    A

    Still waiting for someone to reply please ...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.