What is wrong with this code ? It gives me -1 for the cost to (4,4) from (0,4).


  • 0
    A
    class Solution {
        public int shortestDistance(int[][] a, int[] start, int[] destination) {
            int m = a.length;
            int n = a[0].length;
             int[][] dirs={{0, 1} ,{0, -1}, {-1, 0}, {1, 0}};
            int[][] dp = new int[m][n];
            for (int[] row : dp)
                Arrays.fill(row, Integer.MAX_VALUE);
            dp[start[0]][start[1]] = 0; 
            Queue<int[]> q = new ArrayDeque<>();
            q.offer(start);
            while (q.size() != 0) {
                int[] current = q.poll();
                int x = current[0];
                int y = current[1];
                for (int[] dir : dirs) {
                    int count = 0; 
                    while (x >= 0 && x < m && y >= 0 && y < n && a[x][y] == 0) {
                        x = x + dir[0];
                        y = y + dir[1];
                        count++;
                    }
                    x = x - dir[0];
                    y = y - dir[1];
                    count--; 
                    if ( count + dp[current[0]][current[1]] < dp[x][y]) {
                        dp[x][y] = count + dp[current[0]][current[1]];
                        q.offer(new int[]{x, y});
                    }
                }
            }
    return dp[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : dp[destination[0]][destination[1]];
        }
    }
    

Log in to reply
 

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