[Python] BFS * BFS  | 130ms | beats 95% | Explained & Commented
Lets break the question into simple parts:\n\n1. Lets think that we have no person and we have to find the minimum path between box and the target. Easy right? 
Lets break the question into simple parts:\n\n1. Lets think that we have no person and we have to find the minimum path between box and the target. Easy right? Simple BFS.\n\n2. If you know how to solve the first part, what I actually do is modify first part with few constraints. \n\t* \tI just check whether the box can be shifted to the new position(up, down, left, right)\n\t* \tFor it to be shifted to the new position the person has to be in a corresponding position right?\n\t* \tSo we check if the person can travel from his old position to his corresponding new position(using another BFS). \n\t* \tIf the person can travel to his new position than the box can be shifted, otherwise the box cannot be shifted.\n\n3. We keep repeating step 2 until we reach the target or it is not possible to move the box anymore.\n\nNOTE :  If you know A* algorithm, you can use Euclidean distance as heuristic and use a priority queue instead of normal queue, the worst case time might increase but average case will get better.\n\n\n```\nclass Solution:\ndef minPushBox(self, grid: List[List[str]]) -> int:\n\n    # this loop is to get the coordinates of target, box and person. Nothing else is gained here\n    for i in range(len(grid)):\n        for j in range(len(grid[0])):\n            if grid[i][j] == "T":\n                target = (i,j)\n            if grid[i][j] == "B":\n                box = (i,j)\n            if grid[i][j] == "S":\n                person = (i,j)\n\n    # this function checks whether the given coordinates/indices are valid to go\n    def valid(x,y):\n        return 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!=\'#\'\n\n    # this function checks whether the person can travel from current position to the destination position.\n    # used simple bfs(dfs can also be used here), should be self explainatory if you know BFS.\n    def check(curr,dest,box):\n        que = deque([curr])\n        v = set()\n        while que:\n            pos = que.popleft()\n            if pos == dest: return True\n            new_pos = [(pos[0]+1,pos[1]),(pos[0]-1,pos[1]),(pos[0],pos[1]+1),(pos[0],pos[1]-1)]\n            for x,y in new_pos:\n                if valid(x,y) and (x,y) not in v and (x,y)!=box:\n                    v.add((x,y))\n                    que.append((x,y))\n        return False\n\n    q = deque([(0,box,person)])\n    vis = {box+person}\n    # this is the main bfs which gives us the answer\n    while q :\n        dist, box, person = q.popleft()\n        if box == target: # return the distance if box is at the target\n            return dist\n\n        #these are the new possible coordinates/indices box can be placed in (up, down, right, left).\n        b_coord = [(box[0]+1,box[1]),(box[0]-1,box[1]),(box[0],box[1]+1),(box[0],box[1]-1)]\n        #these are the corresponding coordinates the person has to be in to push .. the box into the new coordinates\n        p_coord = [(box[0]-1,box[1]),(box[0]+1,box[1]),(box[0],box[1]-1),(box[0],box[1]+1)]\n\n        for new_box,new_person in zip(b_coord,p_coord): \n            # we check if the new box coordinates are valid and our current state is not in vis\n            if valid(*new_box) and new_box+box not in vis:\n                # we check corresponding person coordinates are valid and if it is possible for the person to reach the new coordinates\n                if valid(*new_person) and check(person,new_person,box):\n                    vis.add(new_box+box)\n                    q.append((dist+1,new_box,box))\n\n    return -1\n```\n\nTime = Space = O((rows*cols)^2)
['Breadth-First Search', 'Python']