The Maze III

hard matrix dijkstra shortest path

Problem

Ball rolls until a wall or falls into the hole. Return the shortest path (sum of moves) as the lexicographically smallest 'lrud' string, or 'impossible'.

Inputmaze=[[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball=[4,3], hole=[0,1]

Output"lul"

State = (cell); priority by (dist, path). During the slide check whether the hole is on the segment.

maze (rows ; , 0=open, 1=wall)

ball

hole

import heapq
def find_shortest_way(maze, ball, hole):
    R, C = len(maze), len(maze[0])
    DIRS = [(-1,0,"u"),(1,0,"d"),(0,-1,"l"),(0,1,"r")]
    hole = tuple(hole)
    pq = [(0, "", ball[0], ball[1])]
    best = {}
    while pq:
        d, path, x, y = heapq.heappop(pq)
        if (x, y) in best and best[(x, y)] <= (d, path): continue
        best[(x, y)] = (d, path)
        if (x, y) == hole: return path
        for dx, dy, ch in DIRS:
            nx, ny, nd = x, y, 0
            while 0 <= nx+dx < R and 0 <= ny+dy < C and maze[nx+dx][ny+dy] == 0:
                nx += dx; ny += dy; nd += 1
                if (nx, ny) == hole: break
            heapq.heappush(pq, (d + nd, path + ch, nx, ny))
    return "impossible"

function findShortestWay(maze, ball, hole) {
  const R = maze.length, C = maze[0].length;
  const DIRS = [[-1,0,"u"],[1,0,"d"],[0,-1,"l"],[0,1,"r"]];
  const pq = [[0, "", ball[0], ball[1]]];
  const best = new Map();
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0] || (a[1] < b[1] ? -1 : 1));
    const [d, path, x, y] = pq.shift();
    const k = x + "," + y;
    if (best.has(k) && (best.get(k)[0] < d || (best.get(k)[0] === d && best.get(k)[1] <= path))) continue;
    best.set(k, [d, path]);
    if (x === hole[0] && y === hole[1]) return path;
    for (const [dx, dy, ch] of DIRS) {
      let nx = x, ny = y, nd = 0, dropped = false;
      while (nx + dx >= 0 && nx + dx < R && ny + dy >= 0 && ny + dy < C && maze[nx+dx][ny+dy] === 0) {
        nx += dx; ny += dy; nd++;
        if (nx === hole[0] && ny === hole[1]) { dropped = true; break; }
      }
      pq.push([d + nd, path + ch, nx, ny]);
    }
  }
  return "impossible";
}

class Solution {
    public String findShortestWay(int[][] m, int[] ball, int[] hole) {
        int R = m.length, C = m[0].length;
        int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
        String[] CH = {"u","d","l","r"};
        PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        Map best = new HashMap<>();
        pq.offer(new int[]{0, ball[0], ball[1], 0}); // dist, x, y, pathLen
        Map paths = new HashMap<>();
        paths.put((long)ball[0] * C + ball[1], "");
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], x = cur[1], y = cur[2];
            long key = (long)x * C + y;
            String path = paths.get(key);
            if (x == hole[0] && y == hole[1]) return path;
            for (int k = 0; k < 4; k++) {
                int nx = x, ny = y, nd = 0;
                while (nx + DIRS[k][0] >= 0 && nx + DIRS[k][0] < R && ny + DIRS[k][1] >= 0 && ny + DIRS[k][1] < C && m[nx+DIRS[k][0]][ny+DIRS[k][1]] == 0) {
                    nx += DIRS[k][0]; ny += DIRS[k][1]; nd++;
                    if (nx == hole[0] && ny == hole[1]) break;
                }
                long nkey = (long)nx * C + ny;
                String np = path + CH[k];
                int[] cur2 = best.get(nkey);
                int[] cand = new int[]{d + nd, np.length()};
                if (cur2 == null || cur2[0] > cand[0] || (cur2[0] == cand[0] && np.compareTo(paths.getOrDefault(nkey, "~")) < 0)) {
                    best.put(nkey, cand); paths.put(nkey, np);
                    pq.offer(new int[]{d + nd, nx, ny, 0});
                }
            }
        }
        return "impossible";
    }
}

string findShortestWay(vector>& m, vector& ball, vector& hole) {
    int R = m.size(), C = m[0].size();
    vector> DIRS = {{-1,0,0,"u"},{1,0,0,"d"},{0,-1,0,"l"},{0,1,0,"r"}};
    priority_queue, vector>, greater<>> pq;
    pq.push({0, "", ball[0], ball[1]});
    map, pair> best;
    while (!pq.empty()) {
        auto [d, path, x, y] = pq.top(); pq.pop();
        auto it = best.find({x, y});
        if (it != best.end() && (it->second.first < d || (it->second.first == d && it->second.second <= path))) continue;
        best[{x, y}] = {d, path};
        if (x == hole[0] && y == hole[1]) return path;
        for (auto& [dx, dy, _, ch] : DIRS) {
            int nx = x, ny = y, nd = 0;
            while (nx + dx >= 0 && nx + dx < R && ny + dy >= 0 && ny + dy < C && m[nx+dx][ny+dy] == 0) {
                nx += dx; ny += dy; nd++;
                if (nx == hole[0] && ny == hole[1]) break;
            }
            pq.push({d + nd, path + ch, nx, ny});
        }
    }
    return "impossible";
}

Explanation

This is The Maze with two twists: the ball can fall into a hole, and among shortest paths we must return the lexicographically smallest instruction string (made of the letters d, l, r, u). We use Dijkstra where each item carries both a distance and the path string.

The priority queue is ordered by (distance, path). Comparing the path string as the tie-breaker means that when two routes cost the same, the alphabetically smaller instruction string is popped first, which automatically yields the required answer.

For each direction the ball rolls until a wall, but the inner loop also checks: if it passes over the hole mid-slide, it stops there immediately (break). That is why we test the hole inside the slide rather than only at stopping points.

The best map records the best (dist, path) reached for each cell so we skip any worse or equal repeat. The first time we pop the hole cell, its path is optimal and we return it; if the queue drains first, we return "impossible".

Example: from ball = [4,3] to hole = [0,1], rolling up then left then left lands the ball in the hole with the smallest valid instruction string "lul".

Time: O(R·C·max(R,C)·log) Space: O(R·C)