[Python] Solution with detailed thinking
Background\nIn this problem, we are given a grid, there\'re 4 types of element:\n player - \'S\'\n box - \'B\'\n obstacle - \'#\'\n floor - \'.\'\n\nplayer need
### Background\nIn this problem, we are given a grid, there\'re 4 types of element:\n* player - \'S\'\n* box - \'B\'\n* obstacle - \'#\'\n* floor - \'.\'\n\nplayer need to push the box to the final target position, our target is to find the mininum push.\n\nThis is a variant of finding the shortest path from start to the end in a 2-D grid.  In general, this is a unweighted graph search problem. \n* We start from the begining\n* at each position, we search at 4 direction\n* before goes to each position, we need to check if the next position\n\t* out of boundary\n\t* is an obstacle or not\n\t* if visited or not\n* we should stop when reaching to the target position\n\n#### BFS \n\n```\ndirs = {(1,0), (0,1), (-1,0), (0,-1)}\nqueue = collections.deque([(start, 0)])\nvisited = {start}\n\nwhile queue:\n\t(i, j), step = queue.popleft()\n\tif (i,j) == target:\n\t\treturn step\n\tfor dx, dy in dirs:\n\t\tx, y = i+dx, j+dy\n\t\tif isValid(x,y,visited) is False:\n\t\t\tcontinue\n\t\tvisited.add((x,y))\n\t\tqueue.append((x,y,step+1))\nreturn -1\n```\n\n#### DFS\n* i, j the current position\n* visited: from the start to the end, which position are visited\n\n```\ndef dfs(i, j, visited):\n\tif (i,j) == target:\n\t\treturn 0\n\tif isValid(i,j,visited) is False:\n\t\treturn float(\'inf\')\n\tstep = float(\'inf\')\n\tfor dx, dy in dirs:\n\t\tx, y = i+dx, j+dy\n\t\tvisited.add((x,y))\n\t\tstep = min(step, dfs(x,y,visited))\n\t\tvisisted.remove((x,y))\n\treturn step\n```\n\n#### helper function\n```\ndef isValid(i,j,visisted)\n\tif i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):\n\t\treturn False\n\tif (i,j) in visited:\n\t\treturn False\n\tif grid[i][j] == \'#\':\n\t\treturn False\n\treturn True\n```\n\n### Analysis\nThe difference of this problem is that\n* there\'s a player, if the player wants to move the box, he/she needs\n\t*  be able to be on another side of the box\n\nSo for the box, at each position, it can move to 4 directions, but for each directions, the player should be able to reach to another position, so our target is to find if the player can be able to reach to that position. How to do so? This is also a traditional graph search problem. But the only problem is player could not cross the box.That\'s say, box is also an obstacle.\n\nSo the basic structure of the solution is two BFS/DFS. \nThe status of the search be be described by \n* player position\n* box position\n\n```\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        \'\'\'\n            find start pos of box, start pos of player, and the pos of target \n            for box start from the begining, do the graph search\n                if reach to the target, return step\n                else: for each 4 dires, also find the player\'s next pos\n                    check if next box and next player pos is valid or not\n                    also check if next box and next player pos has been recorded before\n                    then push the info for the next move\n\n        \'\'\'\n        m, n = len(grid), len(grid[0])\n        dirs = {(0,1), (1,0), (0,-1), (-1,0)}\n        \n        def get_initials():\n            box, player, target = None, None, None\n            for i in range(m):\n                for j in range(n):\n                    if grid[i][j] == \'S\':\n                        player = (i,j)\n                    if grid[i][j] == \'B\':\n                        box = (i,j)\n                    if grid[i][j] == \'T\':\n                        target = (i,j)\n            \n            return box, player, target\n        \n        def isReacheable(box_i, box_j, player_i, player_j, nxt_player_i, nxt_player_j):\n            tmp = grid[box_i][box_j]\n            grid[box_i][box_j] = \'#\'\n            res = _isReacheable(player_i, player_j, nxt_player_i, nxt_player_j)\n            grid[box_i][box_j] = tmp\n            return res\n        \n        def _isReacheable(start_i, start_j, end_i, end_j):\n            queue = collections.deque([(start_i, start_j)])\n            visited = {(start_i, start_j)}\n            while queue:\n                i, j = queue.popleft()\n                if (i,j) == (end_i, end_j):\n                    return True\n                for dx, dy in dirs:\n                    x, y = i+dx, j+dy\n                    if _isValidPos(x, y, visited):\n                        queue.append((x,y))\n                        visited.add((x,y))\n            return False\n        \n        def _isValidPos(x,y,visited):\n            return 0<=x<m and 0<=y<n and (x,y) not in visited and grid[x][y] != \'#\'\n        \n        def isValidPos(box_i, box_j, player_i, player_j, visited):\n            def isInBoundary(i,j):\n                return  0<=i<m and 0<=j<n\n            \n            return isInBoundary(box_i, box_j) and isInBoundary(player_i, player_j)\\\n                    and (box_i, box_j, player_i, player_j) not in visited\\\n                    and grid[box_i][box_j] != \'#\' and grid[player_i][player_j] != \'#\'\n        \n        \n        (box_i, box_j), (player_i, player_j), target = get_initials()\n        grid[box_i][box_j] = \'.\'\n        grid[player_i][player_j] = \'.\'\n        \n        queue = collections.deque([(box_i, box_j, player_i, player_j, 0)])\n        visited = {(box_i, box_j, player_i, player_j)}\n        while queue:\n            b_i, b_j, p_i, p_j, step = queue.popleft()\n            if (b_i, b_j) == target:\n                return step\n            for dx, dy in dirs:\n                nxt_b_i, nxt_b_j, nxt_p_i, nxt_p_j = b_i+dx, b_j+dy, b_i-dx, b_j-dy\n                if isValidPos(nxt_b_i, nxt_b_j, nxt_p_i, nxt_p_j, visited) is False:\n                    continue\n                if isReacheable(b_i, b_j, p_i, p_j, nxt_p_i, nxt_p_j) is False:\n                    continue\n                queue.append((nxt_b_i, nxt_b_j, nxt_p_i, nxt_p_j, step+1))\n                visited.add((nxt_b_i, nxt_b_j, nxt_p_i, nxt_p_j))\n        return -1\n```
['Depth-First Search', 'Breadth-First Search', 'Python']