Alternative approach using Dijkstra in O(rc max(log r, log c)) time
This problem can also be solved in a more general approach way using Dijkstra.\n\nConstruct a graph G = (V, E) as follows:\nV = all cells plus a dummy vertex, v
This problem can also be solved in a more general approach way using Dijkstra.\n\nConstruct a graph `G = (V, E)` as follows:\nV = all cells plus a dummy vertex, `v`, corresponding to the outside region.\nIf `cell(i, j)` is adjacent to `cell(i', j')`, then add an direct edge from `(i, j)` to `(i', j')` with weight `height(i', j')`.\nAdd an edge with zero weight from any boundary cell to the dummy vertex `v`.\n\nThe weight of a path is defined as the weight of the heaviest edge along it. Then, for any cell `(i, j)`, the height of water it can save is equal to the weight, denoted by `dist(i, j)`, of the shortest path from `(i, j)` to `v`. (If the weight is less than or equal to `height(i, j)`, no water can be accumulated at that particular position.)\n\nWe want to compute the `dist(i, j)` for all pairs of `(i, j)`. Here, we have multiple sources and one destination, but this problem essentially can be solved using one pass of Dijkstra algorithm if we **reverse** the directions of all edges. The graph is sparse, i.e., there are O(rc) edges, resulting an `O(rc log(rc)) = O(rc max(log r, log c))` runtime and using `O(rc)` space.\n\n\nJava Code:\n```Java\npublic class Solution {\n\n    int[] dx = {0, 0, 1, -1};\n    int[] dy = {1, -1, 0, 0};\n\n    List<int[]>[] g;\n    int start;\n\n    private int[] dijkstra() {\n        int[] dist = new int[g.length];\n        Arrays.fill(dist, Integer.MAX_VALUE / 2);\n        dist[start] = 0;\n        TreeSet<int[]> tree = new TreeSet<>((u, v) -> u[1] == v[1] ? u[0] - v[0] : u[1] - v[1]);\n        tree.add(new int[]{start, 0});\n        while (!tree.isEmpty()) {\n            int u = tree.first()[0], d = tree.pollFirst()[1];\n            for (int[] e : g[u]) {\n                int v = e[0], w = e[1];\n                if (Math.max(d, w) < dist[v]) {\n                    tree.remove(new int[]{v, dist[v]});\n                    dist[v] = Math.max(d, w);\n                    tree.add(new int[]{v, dist[v]});\n                }\n            }\n        }\n        return dist;\n    }\n\n    public int trapRainWater(int[][] a) {\n        if (a == null || a.length == 0 || a[0].length == 0) return 0;\n        int r = a.length, c = a[0].length;\n\n        start = r * c;\n        g = new List[r * c + 1];\n        for (int i = 0; i < g.length; i++) g[i] = new ArrayList<>();\n        for (int i = 0; i < r; i++)\n            for (int j = 0; j < c; j++) {\n                if (i == 0 || i == r - 1 || j == 0 || j == c - 1) g[start].add(new int[]{i * c + j, 0});\n                for (int k = 0; k < 4; k++) {\n                    int x = i + dx[k], y = j + dy[k];\n                    if (x >= 0 && x < r && y >= 0 && y < c) g[i * c + j].add(new int[]{x * c + y, a[i][j]});\n                }\n            }\n\n        int ans = 0;\n        int[] dist = dijkstra();\n        for (int i = 0; i < r; i++)\n            for (int j = 0; j < c; j++) {\n                int cb = dist[i * c + j];\n                if (cb > a[i][j]) ans += cb - a[i][j];\n            }\n\n        return ans;\n    }\n}\n```
['Java']