Java A* Search
\n /*\n \n  Idea:\n    concern:\n    1> how to avoid repeat or endless loop of person walking and box moving\n     answer: S can repeat location when B is in di
```\n /*\n \n  Idea:\n    concern:\n    1> how to avoid repeat or endless loop of person walking and box moving\n     answer: S can repeat location when B is in different location,\n             but for a given fix B location, S should not repeat  walking\n             B should not repeat moving.\n             need a visited variable to keep the visited status using box and person location\n    2> if failed to move to any direction should restore the B to one of original location?\n     answer: yeah, only when there is not any direction is possible to move on.\n             the one of original location is decided by the priority value of heuristic\n             So should keep Box and person location in status.\n             heuristic decided by moved steps and manhattan distance.\n             so the status include: manhattan distance, moved steps, Box and person location\n\n   Solution:\n    find the initial location of B, S, T\n    A * search: BFS + priority queue.\n                a priority queue keeping status  and heuristic ( manhattan + steps)\n                avoid repeating visited status: locations of person and box\n      initial status in priority queue\n      loop while queue is not empty\n        1> if current B is T then return moved steps\n        2> if current B is visited return, stop trying from this status\n        3> make person + B location as visited\n          try a step toward 4 direction of person.\n            effective: try to move box a step toward 4 directions if box\n                       have space to move & person can walk to the place to push\n            details:\n            from current status: person try walk a step toward 4 directions if\n            person can walk: in grid and no # at next cell\n            if the next cell for person to walk is box location and box\'s next cell\n            is allow it to move:\n               it is move box\n            else\n               it is only person walk.\n            update related status and add to priority queue.\n\n     out of loop return -1\n     Variables:\n      target T location [A,B],\n      person S location [c,r] or [column, row]\n      box B location [a,b]\n  */\n  int A = 0, B = 0;\n  int[][] d4 = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};\n\n  public int minPushBox(char[][] grid) {\n    int R = grid.length, C = grid[0].length;\n    // searching initial location T[A,B], B[ia,ib],S[ix,iy]\n    int ia = 0, ib = 0, ix = 0, iy = 0;\n    for (int i = 0; i < R; i++) {\n      for (int j = 0; j < C; j++) {\n        char c = grid[i][j];\n        if (c == \'T\') {\n          A = j;\n          B = i;\n        }\n        if (c == \'B\') {\n          ia = j;\n          ib = i;\n        }\n        if (c == \'S\') {\n          ix = j;\n          iy = i;\n        }\n      }\n    }\n\n    Set<String> v = new HashSet();\n    Queue<int[]> q = new PriorityQueue<>((o, o2) -> o[0] + o[1] - o2[0] - o2[1]);\n    q.offer(new int[] {Math.abs(ia - A) + Math.abs(ib - B), 0, ix, iy, ia, ib});\n    while (!q.isEmpty()) {\n      int[] c = q.poll();\n      int a = c[4], b = c[5], steps = c[1];\n      if (a == A && b == B) return steps;\n\n      int x = c[2], y = c[3];\n      String k = x + "" + y + "" + a + "" + b;\n      if (v.contains(k)) continue;\n      v.add(k);\n\n      for (int[] d : d4) {\n        int nx = x + d[0], ny = y + d[1];\n        if (!canWalk(nx, ny, R, C, grid)) continue;\n        if (nx == a && ny == b) {\n          int na = a + d[0], nb = b + d[1];\n          if (!canWalk(na, nb, R, C, grid)) continue;\n          q.offer(new int[] {Math.abs(na - A) + Math.abs(nb - B), steps + 1, nx, ny, na, nb});\n        } else q.offer(new int[] {c[0], steps, nx, ny, a, b});\n      }\n    }\n    return -1;\n  }\n\n  private boolean canWalk(int x, int y, int R, int C, char[][] grid) {\n    if (x < 0 || x >= C || y < 0 || y >= R || grid[y][x] == \'#\') return false;\n    return true;\n  } \n```
[]