Shortest Absolute Value Distance - Google Top Interview Questions

                        Solution in C++ :

int solve(vector<vector<int>>& mat) {
    int n = mat.size(), m = mat[0].size();
    vector<vector<int>> dist(n, vector<int>(m, 1e9));
    set<pair<int, pair<int, int>>> s;
    s.insert({0, {0, 0}});
    dist[0][0] = 0;
    vector<int> dir{0, -1, 0, 1, 0};
    while (!s.empty()) {
        auto [dis, cor] = *s.begin();
        s.erase(s.begin());
        auto [i, j] = cor;
        for (int k = 0; k < 4; k++) {
            int x = i + dir[k], y = j + dir[k + 1];
            if (x >= 0 and x < n and y >= 0 and y < m and
                dist[x][y] > dist[i][j] + abs(mat[x][y] - mat[i][j])) {
                if (s.find({dist[x][y], {x, y}}) != s.end()) {
                    s.erase(s.find({dist[x][y], {x, y}}));
                }
                dist[x][y] = dist[i][j] + abs(mat[x][y] - mat[i][j]);
                s.insert({dist[x][y], {x, y}});
            }
        }
    }
    return dist[n - 1][m - 1];
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    class Node {
        int r, c;
        long dist;
        Node(int r, int c, long dist) {
            this.r = r;
            this.c = c;
            this.dist = dist;
        }
    }
    boolean valid(int r, int c, int m, int n) {
        if (r < 0 || c < 0 || r >= m || c >= n)
            return false;
        return true;
    }
    int[] dr = {0, 0, 1, -1};
    int[] dc = {1, -1, 0, 0};
    public int solve(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> (Long.compare(a.dist, b.dist)));
        boolean[][] vis = new boolean[m][n];
        long[][] dists = new long[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(dists[i], 100000000);
        vis[0][0] = false;
        pq.add(new Node(0, 0, 0));
        dists[0][0] = 0;
        while (pq.size() > 0 && !vis[m - 1][n - 1]) {
            Node curnode = pq.poll();
            int r = curnode.r;
            int c = curnode.c;
            long d = curnode.dist;
            if (vis[r][c])
                continue;
            vis[r][c] = true;
            for (int z = 0; z < 4; z++) {
                int nr = r + dr[z];
                int nc = c + dc[z];
                if (!valid(nr, nc, m, n) || vis[nr][nc])
                    continue;
                if (d + Math.abs(matrix[r][c] - matrix[nr][nc]) < dists[nr][nc]) {
                    dists[nr][nc] = d + Math.abs(matrix[r][c] - matrix[nr][nc]);
                    pq.add(new Node(nr, nc, dists[nr][nc]));
                }
            }
        }

        return (int) dists[m - 1][n - 1];
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, matrix):
        m, n = len(matrix), len(matrix[0])

        def neighbours(i, j):
            dr = ((i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1))
            return [(x, y) for x, y in dr if 0 <= x < m and 0 <= y < n]

        visited = [[False for j in range(n)] for i in range(m)]
        distance = [[float("inf") for j in range(n)] for i in range(m)]
        distance[0][0] = 0
        pq = []
        heapq.heapify(pq)
        heapq.heappush(pq, (0, 0, 0))  # (distance,i index, j index)
        while not visited[m - 1][n - 1]:
            dist, i, j = heapq.heappop(pq)
            if visited[i][j]:
                continue
            visited[i][j] = True
            if i == m - 1 and j == n - 1:
                break
            for x, y in neighbours(i, j):
                dist = distance[i][j] + abs(matrix[i][j] - matrix[x][y])
                if not visited[x][y] and dist < distance[x][y]:
                    distance[x][y] = dist
                    heapq.heappush(pq, (dist, x, y))
        return dist