Python3 2-level BFS, a few notes
A few key points that distinguishes this problem from your typical BFS:\n\n1. To push the box to a specific direction, player has to be at the opposite directio
A few key points that distinguishes this problem from your typical BFS:\n\n1. To push the box to a specific direction, player has to be at the opposite direction. So there needs be empty space on both sides\n\n2. Player has to be able to find a path from previous position to the needed position described in point 1 above\n\n3. Box position changes everytime players moves it, which affects point 2 above\n\n4, Box can return to a previous location if coming from different direction.\n\n```\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n      h = len(grid)\n      w = len(grid[0])\n      \n      target, box, player = (0,0), (0,0), (0,0)\n      for row in range(h):\n        for col in range(w):\n          if grid[row][col] == \'B\':\n            cur = (row, col)\n          if grid[row][col] == \'T\':\n            target = (row, col)\n          if grid[row][col] == \'S\':\n            player = (row, col)\n\n      dirs = [(0, 1), (0, -1), (1, 0), (-1 ,0)]\n      \n      def has_path(pos, target):\n        # print(grid)\n        myq = [pos]\n        visited = set()\n        while myq:\n          cur = myq.pop(0)\n          if cur == target:\n            return True\n          for dir in dirs:\n            new_pos = (cur[0] + dir[0], cur[1] + dir[1])\n            if new_pos[0] >= 0 and new_pos[0] < h and new_pos[1] >= 0 and new_pos[1] < w:\n              if grid[new_pos[0]][new_pos[1]] != \'#\' and grid[new_pos[0]][new_pos[1]] != \'B\' and new_pos not in visited:\n                myq.append(new_pos)\n                visited.add(new_pos)\n        return False\n\n      myq = [(cur, player, 0)]\n      visited = set()\n      grid[box[0]][box[1]] = \'.\' \n      \n      while myq:\n        box, player, cur_round = myq.pop(0)\n        if box == target:\n          return cur_round\n        grid[box[0]][box[1]] = \'B\' # \u83B7\u5F97\u5F53\u524D\u7BB1\u5B50\u7684\u4F4D\u7F6E\n        for dir in dirs:\n          new_pos = (box[0] + dir[0], box[1] + dir[1])\n          oppo_pos = (box[0] - dir[0], box[1] - dir[1])\n          if new_pos[0] >= 0 and new_pos[0] < h and new_pos[1] >= 0 and new_pos[1] < w:\n            if oppo_pos[0] >= 0 and oppo_pos[0] < h and oppo_pos[1] >= 0 and oppo_pos[1] < w:\n              # \u5982\u679C\u6765\u7684\u65B9\u5411\u4E0D\u540C\uFF0C\u90A3\u4E48\u7BB1\u5B50\u53EF\u4EE5\u56DE\u5230\u4E4B\u524D\u7ECF\u8FC7\u5230\u8FC7\u7684\u4F4D\u7F6E\n              if grid[new_pos[0]][new_pos[1]] != \'#\' and grid[oppo_pos[0]][oppo_pos[1]] != \'#\' and (new_pos, box) not in visited: \n                if has_path(player, oppo_pos): # player \u80FD\u5426\u5230\u8FBE\u9700\u8981\u5230\u8FBE\u7684\u4F4D\u7F6E\n                  myq.append((new_pos, box, cur_round + 1))# \u63A8\u5B8C\u7BB1\u5B50\u540Eplayer\u5904\u4E8Ebox\u539F\u672C\u7684\u4F4D\u7F6E\n                  # print(box, \'->\', new_pos)\n                  visited.add((new_pos, box))\n        grid[box[0]][box[1]] = \'.\'\n      return -1\n                           \n                           \n              \n            \n        \n      \n```
[]