title: How to find the shortest path in a puzzle with keys and doors
body: <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>