Apply BFS twice - with some helpful hints
Algorithm:\n1. Choose the location of the box, \n2. Then, new person location should be opposite to that of the box.\n3. Then ask the algorithm - (can_reach def
**Algorithm**:\n1. Choose the location of the box, \n2. Then, new person location should be opposite to that of the box.\n3. Then ask the algorithm - (can_reach def) Can I reach to new_person from current person location? Only if the answer is \'yes\', consider that new box location.\n\n```\nclass Solution:\n    def minPushBox(self, grid: List[List[str]]) -> int:\n        self.nRow, self.nCol = len(grid), len(grid[0])\n        DIR = [-1,0,1,0,-1]\n        \n        # find out the location of box and the person and the target\n        for i in range(self.nRow):\n            for j in range(self.nCol):\n                if grid[i][j] == \'S\':\n                    person = (i,j)\n                if grid[i][j] == \'B\':\n                    box = (i,j)\n                if grid[i][j] == \'T\':\n                    target = (i,j)\n        \n        def is_valid(pos):\n            pos_x, pos_y = pos\n            if pos_x < 0 or pos_y < 0 or pos_x >= self.nRow or pos_y >= self.nCol or grid[pos_x][pos_y] == \'#\':\n                return False\n            return True\n        \n        def can_reach(curr_loc, new_loc, box_loc):\n            \'\'\'\n            Can I reach to new location from the current location?\n            \'\'\'\n            _q = deque()\n            _v = set()\n            _q.append(curr_loc)\n            _v.add(curr_loc)\n            \n            while _q:\n                curr_loc = _q.popleft()\n                if curr_loc == new_loc:\n                    return True\n                curr_loc_x, curr_loc_y = curr_loc\n                for d in range(4):\n                    ncurr_loc_x, ncurr_loc_y = curr_loc_x + DIR[d], curr_loc_y + DIR[d+1]\n                    ncurr_loc = (ncurr_loc_x, ncurr_loc_y)\n                    if is_valid(ncurr_loc) and ncurr_loc != box_loc and ncurr_loc not in _v:\n                        _q.append(ncurr_loc)\n                        _v.add(ncurr_loc)\n            return False\n        \n        q = deque()\n        visited = set()\n        q.append((0, box, person)) # start location\n        visited.add((box, person))\n        \n        while q:\n            dist, box, person = q.popleft()\n            box_x, box_y = box\n            person_x, person_y = person\n            \n            if box == target:\n                return dist\n            \n            for d in range(4):\n                new_box_x, new_box_y = box_x + DIR[d] , box_y + DIR[d+1]\n                # now new person location should be opposite to that of the box\n                new_person_x, new_person_y = box_x - DIR[d] , box_y - DIR[d+1]\n                \n                new_box = (new_box_x, new_box_y)\n                new_person = (new_person_x, new_person_y)\n                \n                if is_valid(new_box) and is_valid(new_person) and can_reach(person, new_person, box) and grid[new_box_x][new_box_y] != \'#\' and (new_box, new_person) not in visited:\n                    q.append((dist+1, new_box, new_person)) \n                    visited.add((new_box, new_person))\n            \n        return -1    \n        \n```\n\nComplexity O(M*N*M*N)
[]