Daily LeetCode Problems: Problem 864. Shortest Path to Get All Keys

Unlocking the Shortest Path: Solving the Shortest Path to Get All Keys Problem

Introduction:

Welcome to another exciting problem-solving article! Today, we’ll dive into problem 864 from LeetCode, titled “Shortest Path to Get All Keys.” This problem challenges us to find the shortest path to collect all the keys in a grid while avoiding walls and locks. We’ll carefully analyze the problem statement, devise an optimal approach, provide step-by-step pseudocode, explain the underlying concepts, and discuss the complexity analysis.

Problem Statement:

The problem presents us with a grid where certain cells are empty, walls, starting points, lowercase letters representing keys, or uppercase letters representing locks. Our goal is to find the lowest number of moves required to collect all the keys. We can move in the four cardinal directions but cannot move outside the grid or walk into walls. We can only walk over a lock if we have its corresponding key.

The grid guarantees that there is exactly one key for each lock and vice versa, and the letters used to represent keys and locks follow the order of the English alphabet. We need to return the lowest number of moves required to collect all the keys. If it is impossible to collect all the keys, we should return -1.

Approach:

To solve this problem, we can utilize a breadth-first search (BFS) algorithm to explore the grid and find the shortest path to collect all the keys. We’ll start from the starting point, keep track of the visited cells and keys collected, and expand the search to neighboring cells.

Pseudocode:

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        rows, cols = len(grid), len(grid[0])
        start_x, start_y = -1, -1
        num_keys = 0
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = set()
        queue = deque()
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '@':
                    start_x, start_y = i, j
                elif grid[i][j].islower():
                    num_keys += 1
        
        state = (start_x, start_y, 0)
        queue.append(state)
        visited.add(state)
        steps = 0
        
        while queue:
            size = len(queue)
            
            for _ in range(size):
                curr_x, curr_y, curr_keys = queue.popleft()
                
                if curr_keys == (1 << num_keys) - 1:
                    return steps
                
                for dx, dy in directions:
                    next_x, next_y = curr_x + dx, curr_y + dy
                    
                    if not is_valid(next_x, next_y, rows, cols, grid, visited, curr_keys):
                        continue
                    
                    next_keys = curr_keys
                    cell = grid[next_x][next_y]
                    
                    if cell.islower():
                        next_keys |= (1 << (ord(cell) - ord('a')))
                    
                    if cell.isupper() and not (curr_keys & (1 << (ord(cell) - ord('A')))):
                        continue
                    
                    next_state = (next_x, next_y, next_keys)
                    
                    if next_state not in visited:
                        visited.add(next_state)
                        queue.append(next_state)
            
            steps += 1
        
        return -1

    def is_valid(x, y, rows, cols, grid, visited, keys):
        return 0 <= x < rows and 0 <= y < cols and grid[x][y] != '#' and (x, y, keys) not in visited

Explanation:

Let’s walk through the pseudocode to understand the approach and its implementation:

1. We start by initializing necessary variables such as the grid dimensions, the starting position, the number of keys, a list of directions, a set to track visited cells, and a queue for BFS.
2. We iterate through the grid to find the starting position and count the number of keys.
3. We create a tuple state containing the starting position and the current keys collected. We add it to the queue and mark it as visited.
4. We begin the BFS loop, which continues until the queue is empty.
5. At each iteration, we process the cells currently in the queue. We store the size of the queue to process each level separately.
6. We extract the current cell’s position and keys from the queue.
7. If all keys have been collected, we return the number of steps taken to reach this state.
8. We iterate through the neighboring cells using the directions array.
9. We check if the neighboring cell is valid and not visited, and if the path is accessible based on the current keys.
10. We update the keys based on the cell type: if it is a lowercase letter (key), we add it to the current keys; if it is an uppercase letter (lock), we check if the corresponding key has been collected.
11. We create a new state for the neighboring cell and add it to the queue if it hasn’t been visited before.
12. We increment the number of steps taken.
13. If no path is found to collect all the keys, we return -1.

Complexity Analysis:

Let’s analyze the time and space complexity of our approach:

• Time Complexity: In the worst case, we visit each cell of the grid only once. Therefore, the time complexity is O(rows * cols * 2^num_keys), where rows and cols are the dimensions of the grid and num_keys is the number of keys.
• Space Complexity: We use additional space to store the visited cells and the queue. The space complexity is O(rows * cols * 2^num_keys).

Full Solution

Python

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m=len(grid)
        n=len(grid[0])
        arr=deque([])
        numOfKeys=0
        keys={'a':0,'b':1,'c':2,'d':3,'e':4,'f':5}
        locks={'A':0,'B':1,'C':2,'D':3,'E':4,'F':5}
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='@':
                    arr.append((i,j,0,0))
                elif grid[i][j] in keys:
                    numOfKeys+=1

        visited=set()
        while arr:
            size=len(arr)
            for _ in range(size):
                i,j,found,steps=arr.popleft()
                curr=grid[i][j]
                if curr in locks and not (found>>locks[curr]) & 1 or curr=='#':
                    continue

                if curr in keys:
                    found |=1<<keys[curr]
                    if found==(1<<numOfKeys)-1:
                        return steps

                for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
                    if 0<=x<m and 0<=y<n and (x,y,found) not in visited:
                        visited.add((x,y,found))
                        arr.append((x,y,found,steps+1))

        return -1                                            

Java

class T {
  public int i;
  public int j;
  public int keys; // Keys in bitmask
  public T(int i, int j, int keys) {
    this.i = i;
    this.j = j;
    this.keys = keys;
  }
}

class Solution {
  public int shortestPathAllKeys(String[] grid) {
    final int m = grid.length;
    final int n = grid[0].length();
    final int keysCount = getKeysCount(grid);
    final int kKeys = (1 << keysCount) - 1;
    final int[] dirs = {0, 1, 0, -1, 0};
    final int[] start = getStart(grid);
    int ans = 0;
    Queue<T> q = new ArrayDeque<>(Arrays.asList(new T(start[0], start[1], 0)));
    boolean[][][] seen = new boolean[m][n][kKeys];
    seen[start[0]][start[1]][0] = true;

    while (!q.isEmpty()) {
      ++ans;
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek().i;
        final int j = q.peek().j;
        final int keys = q.poll().keys;
        for (int k = 0; k < 4; ++k) {
          final int x = i + dirs[k];
          final int y = j + dirs[k + 1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          final char c = grid[x].charAt(y);
          if (c == '#')
            continue;
          final int newKeys = 'a' <= c && c <= 'f' ? keys | 1 << c - 'a' : keys;
          if (newKeys == kKeys)
            return ans;
          if (seen[x][y][newKeys])
            continue;
          if ('A' <= c && c <= 'F' && (newKeys >> c - 'A' & 1) == 0)
            continue;
          q.offer(new T(x, y, newKeys));
          seen[x][y][newKeys] = true;
        }
      }
    }

    return -1;
  }

  private int getKeysCount(String[] grid) {
    int count = 0;
    for (final String s : grid)
      count += (int) s.chars().filter(c -> 'a' <= c && c <= 'f').count();
    return count;
  }

  private int[] getStart(String[] grid) {
    for (int i = 0; i < grid.length; ++i)
      for (int j = 0; j < grid[0].length(); ++j)
        if (grid[i].charAt(j) == '@')
          return new int[] {i, j};
    throw new IllegalArgumentException();
  }
}

C++

struct T {
  int i;
  int j;
  int keys;  // Keys in bitmask
  T(int i, int j, int keys) : i(i), j(j), keys(keys) {}
};

class Solution {
 public:
  int shortestPathAllKeys(vector<string>& grid) {
    const int m = grid.size();
    const int n = grid[0].length();
    const int keysCount = getKeysCount(grid);
    const int kKeys = (1 << keysCount) - 1;
    const vector<int> dirs{0, 1, 0, -1, 0};
    const vector<int> start = getStart(grid);
    int ans = 0;
    queue<T> q{{{start[0], start[1], 0}}};
    vector<vector<vector<bool>>> seen(
        m, vector<vector<bool>>(n, vector<bool>(kKeys)));
    seen[start[0]][start[1]][0] = true;

    while (!q.empty()) {
      ++ans;
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j, keys] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
          const int x = i + dirs[k];
          const int y = j + dirs[k + 1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          const char c = grid[x][y];
          if (c == '#')
            continue;
          const int newKeys = 'a' <= c && c <= 'f' ? keys | 1 << c - 'a' : keys;
          if (newKeys == kKeys)
            return ans;
          if (seen[x][y][newKeys])
            continue;
          if ('A' <= c && c <= 'F' && ((newKeys >> c - 'A') & 1) == 0)
            continue;
          q.emplace(x, y, newKeys);
          seen[x][y][newKeys] = true;
        }
      }
    }

    return -1;
  }

 private:
  int getKeysCount(const vector<string>& grid) {
    int count = 0;
    for (const string& s : grid)
      count += std::count_if(s.begin(), s.end(),
                             [](char c) { return 'a' <= c && c <= 'f'; });
    return count;
  }

  vector<int> getStart(const vector<string>& grid) {
    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].length(); ++j)
        if (grid[i][j] == '@')
          return {i, j};
    throw;
  }
};

Conclusion:

In this article, we tackled problem 864, “Shortest Path to Get All Keys,” from LeetCode. We learned how to navigate a grid, collect keys, and unlock locks while finding the shortest path. By employing a BFS algorithm and carefully managing our state, we can efficiently solve this problem. I hope you found this article informative and that it helps you improve your problem-solving skills. Stay tuned for more exciting LeetCode challenges in our daily series. Happy coding!