How to find the shortest path in a puzzle with keys and doors
<p>I tried the below code, but it didn't give me the right answer.</p>

<p>Here is the problem statement. </p>

<blockquote>
  <p>Suppose you have a 2-D grid. Each point is either land or water. There
  is also a start point and a goal.</p>
  
  <p>There are now keys that open up doors. Each key corresponds to one
  door.</p>
  
  <p>Implement a function that returns the shortest path from the start to
  the goal using land tiles, keys and open doors.</p>
  
  <p>Data Representation </p>
  
  <p>The map will be passed as an array of strings.</p>
  
  <p>A map can have the following tiles.</p>
  
  <p><code>0 = Water</code> <code>1 = Land</code> <code>2 = Start</code> <code>3 = Goal</code> <code>uppercase = door</code>
  <code>lowercase = key</code> </p>
  
  <p>The grid can be like this:</p>

<pre><code>            {{'0', '2', '1', '1', '1'},
            {'0', '1', '0', '0', '1'},
            {'0', '0', '0', '0', '1'},
            {'0', '0', 'A', '0', '1'},
            {'1', '1', 'a', '1', '1'},
            {'1', 'b', '0', '0', 'B'},
            {'1', '1', '0', '0', '1'},
            {'0', '1', '0', '0', '3'}};
</code></pre>
  
  <p>So the shortest path should be:
  01->02->03->04->14->24->34->44->43->42->41->51->41->42->43->44->54->64->74</p>
</blockquote>

<p>And my codes go like:</p>

<pre><code>public class shortestPath {
    static int shortest = Integer.MAX_VALUE;
    static String path = "";
    static ArrayList&lt;ArrayList&lt;int[]&gt;&gt; res = new ArrayList&lt;ArrayList&lt;int[]&gt;&gt;();

    public static void main(String[] args) {
        char[][] board = {{'0', '2', '1', '1', '1'},
                {'0', '1', '0', '0', '1'},
                {'0', '0', '0', '0', '1'},
                {'0', '0', 'A', '0', '1'},
                {'1', '1', 'a', '1', '1'},
                {'1', 'b', '0', '0', 'B'},
                {'1', '1', '0', '0', '1'},
                {'0', '1', '0', '0', '3'}};
        System.out.println(findShortest(board));
        System.out.println(path);

    }

    public static int findShortest(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return 0;
        int row = board.length;
        int col = board[0].length;
        int[] start = new int[2];
        int[] end = new int[2];
        int[][] visited = new int[row][col];
        HashMap&lt;Character, ArrayList&lt;int[]&gt;&gt; hm = new HashMap&lt;&gt;();
        for (int i = 0; i &lt; row; i++) {
            for (int j = 0; j &lt; col; j++) {
                if (board[i][j] == '2') {
                    start = new int[]{i, j};
                }
                if (board[i][j] == '3') {
                    end = new int[]{i, j};
                }
                if (Character.isUpperCase(board[i][j])) {
                    char key = Character.toLowerCase(board[i][j]);
                    if (hm.containsKey(key)) {
                        hm.get(key).add(new int[]{i, j});
                    } else {
                        ArrayList&lt;int[]&gt; al = new ArrayList&lt;&gt;();
                        al.add(new int[]{i, j});
                        hm.put(key, al);
                    }
                    board[i][j] = '0';
                }
            }
        }
        //HashSet&lt;Character&gt; hs = new HashSet&lt;Character&gt;();
        //helper2(board, hs, start[0], start[1], row, col, 0, visited, new StringBuilder(), new ArrayList&lt;int[]&gt;(), res);
        helper(board, hm, start[0], start[1], row, col, 0, visited, new StringBuilder());
        return shortest;
    }

    public static void helper(char[][] board, HashMap&lt;Character, ArrayList&lt;int[]&gt;&gt; hm, int r, int c, int row, int col, int count, int[][] visited, StringBuilder sb) {
        // System.out.println(r + " " + c);
        visited[r][c] = visited[r][c] + 1;
        sb.append(r).append(c).append("-&gt;");
        if (board[r][c] == '3') {
            System.out.println(count);
            if (shortest &gt; count) {
                path = sb.deleteCharAt(sb.length() - 1).deleteCharAt(sb.length() - 1).toString();
                sb.append("-&gt;");
                shortest = count;
            }
            //return;
            //shortest = Math.min(shortest, count);
        }
        if (Character.isLowerCase(board[r][c])) {  // if this is the key;
            if (hm.containsKey(board[r][c])) {
                for (int[] i : hm.get(board[r][c])) {
                    board[i[0]][i[1]] = '1';
                }
            }
        }
        if (r + 1 &lt; row &amp;&amp; board[r + 1][c] != '0' &amp;&amp; visited[r + 1][c] &lt; 2) {
            helper(board, hm, r + 1, c, row, col, count + 1, visited, sb);
        }
        if (c + 1 &lt; col &amp;&amp; board[r][c + 1] != '0' &amp;&amp; visited[r][c + 1] &lt; 2) {
            helper(board, hm, r, c + 1, row, col, count + 1, visited, sb);
        }
        if (r - 1 &gt;= 0 &amp;&amp; board[r - 1][c] != '0' &amp;&amp; visited[r - 1][c] &lt; 2) {
            helper(board, hm, r - 1, c, row, col, count + 1, visited, sb);
        }
        if (c - 1 &gt;= 0 &amp;&amp; board[r][c - 1] != '0' &amp;&amp; visited[r][c - 1] &lt; 2) {
            helper(board, hm, r, c - 1, row, col, count + 1, visited, sb);
        }
        visited[r][c] = visited[r][c] - 1;
        sb.delete(sb.length() - 4, sb.length());
        if (Character.isLowerCase(board[r][c])) {  // if this is the key;
            if (hm.containsKey(board[r][c])) {
                for (int[] i : hm.get(board[r][c])) {
                    board[i[0]][i[1]] = '0';
                }
            }
        }
        return;
    }


}
</code></pre>