864. Shortest Path to Get All Keys (H)

You are given an m x n grid grid where:

• '.' is an empty cell.

• '#' is a wall.

• '@' is the starting point.

• Lowercase letters represent keys.

• Uppercase letters represent locks.

You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.

For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return -1.

Example 1:

Input: grid = ["@.a.#","###.#","b.A.B"]
Output: 8
Explanation: Note that the goal is to obtain all the keys not to open all the locks.

Example 2:

Input: grid = ["@..aA","..B#.","....b"]
Output: 6

Example 3:

Input: grid = ["@Aa"]
Output: -1

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 30

• grid[i][j] is either an English letter, '.', '#', or '@'.

• The number of keys in the grid is in the range [1, 6].

• Each key in the grid is unique.

• Each key in the grid has a matching lock.

Solution:

https://www.jiuzhang.com/problem/shortest-path-to-get-all-keys/

Implemented using a StringBuilder to keep track of keys, instead of a bit mask. Not as efficient, but maybe easier to read/implement during an interview? Then use the bit mask for bonus points. =D

class Solution {
    public int shortestPathAllKeys(String[] grid) {
        
        String emptyString = "      ";
        String all6Keys = "abcdef";
        
        Queue<Node> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        int startX =0;
        int startY = 0;
        int maxLen = 0;
        for(int i = 0; i< grid.length; i++)
        {
            for(int j = 0; j< grid[0].length(); j++)
            {
                char c = grid[i].charAt(j);
                
                if(c >='a' && c <='f')
                {
                    maxLen = Math.max(maxLen, c - 'a' + 1);
                }
                if(c == '@')
                {
                    startX = i;
                    startY = j;
                }
            }
        }
        
        String allKeys = all6Keys.substring(0, maxLen);
        Node startNode = new Node(startX, startY, new StringBuilder(emptyString.substring(0, maxLen)));
        queue.offer(startNode);
        visited.add(startNode.toString());
        
        
        int step = 0;
        int[] directX = {-1,1,0,0};
        int[] directY = {0,0,-1,1};
        while(!queue.isEmpty())
        {
            int size = queue.size();
            for(int j= 0;j< size; j++)
            {
                Node current = queue.poll();
                if(allKeys.equals(current.keySb.toString()))
                {
                    return step;
                }
                for(int i = 0; i< 4; i++)
                {
                    int nextX = current.x + directX[i];
                    int nextY = current.y + directY[i];
                     // 这里不能如下用， 要再new 一个新的出来。
                    //StringBuilder currentKeys = current.keySb;
                    StringBuilder currentKeys = new StringBuilder(current.keySb);
                    
                    if(isBound(grid, nextX, nextY) && grid[nextX].charAt(nextY) != '#')
                    {
                        Character c = grid[nextX].charAt(nextY);
                        
                        // encounter lock and current don't have key
                        if(isLock(c) && currentKeys.charAt(Character.toLowerCase(c)-'a') != Character.toLowerCase(c))
                        {
                            continue;
                        }
                        
                        // encounter key, add it in the queue and acquiredKeys
                        if(isKey(c))
                        {
                            currentKeys.setCharAt(c-'a', c);
                        }
                        
                        Node adj = new Node(nextX, nextY, currentKeys);
                        if(!visited.contains(adj.toString()))
                        {
                            queue.offer(adj);
                            visited.add(adj.toString());
                        }     
                    }
                }
             }
            step++;
        }
        return -1;
    }
    
    public boolean isKey(Character c)
    {
        if(c >= 'a' && c <= 'f')
        {
            return true;
        }
        return false;
    }
    
    public boolean isLock(Character c)
    {
        if(c >= 'A' && c <= 'F')
        {
            return true;
        }
        return false;
    }
    
    public boolean isBound(String[] grid, int x, int y)
    {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length();
    }

}

class Node
{
    int x;
    int y; 
    StringBuilder keySb;
    
    public Node(int x, int y, StringBuilder sb)
    {
        this.x = x;
        this.y = y;
        this.keySb = sb;
    }
    
    
    public String toString()
    {
        //这里一定要append ",", 不然当keySb is "   ", 前面的空格会消失
        return new StringBuilder(this.keySb).append(",").append(this.x).append(",").append(this.y).toString();
        //return new StringBuilder(this.keySb).append(this.x).append(this.y).toString();
    }
}

Pinterest Phone:

简化版： 只有一把钥匙， a和A，Node里面只要加上isGetKey boolean就行了

import java.util.*;

public class ShortPathGetOneKey {

    public static void main(String[] args)
    {
        char[][] maze = {{'0','a','0'}, {'A','1','1'}, {'0','0','0'}};
        int path = getShortPath(maze);
        // output 6;
        System.out.println(path);
    }

    public static int getShortPath(char[][] maze)
    {

        int m = maze.length;
        int n = maze[0].length;

      
        Set<String> visited = new HashSet<>();
        Queue<Node> queue = new LinkedList<Node>();
        Node startNode = new Node(0, 0, false);
        queue.offer(startNode);
        visited.add(startNode.toString());

        
        int step = 0;
        int[] directX = {-1, 1, 0, 0};
        int[] directY = {0, 0, -1, 1};
        while(!queue.isEmpty())
        {
            int size = queue.size();
            for(int j = 0; j< size; j++)
            {
                Node current = queue.poll();
                System.out.println(current.toString());
                if(current.x == m-1 && current.y == n-1)
                {
                    return step;
                }

                for(int i = 0; i< 4; i++)
                {
                    int nextX = current.x + directX[i];
                    int nextY = current.y + directY[i];
                    if(nextX <0 || nextX >=m || nextY <0 || nextY >=n)
                    {
                        continue;
                    }
                    char c = maze[nextX][nextY];
                    
                    if(c == '1')
                    {
                        continue;
                    }
 
                    if(c  == 'A' && !current.isGetKey)
                    {   
                        continue;
                    }

                    Node adj = new Node(nextX, nextY, current.isGetKey);

                    if(c == 'a')
                    {
                        adj.isGetKey = true;
                    }

                    if(!visited.contains(adj.toString()))
                    {
                        queue.offer(adj);
                        visited.add(adj.toString());
                    }
                }
            }
            step++;
        }
        return -1;
    }
    
}

class Node
{
    int x; 
    int y;
    boolean isGetKey;

    public Node(int x, int y, boolean isGetKey)
    {
        this.x = x;
        this.y = y;
        this.isGetKey = isGetKey;
    }

    public String toString()
    {
        if(this.isGetKey)
        {
            return new StringBuilder().append(x).append(y).append("1").toString();
        }
        return new StringBuilder().append(x).append(y).append("0").toString();
    }
}