Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.
The game is represented by a grid of size m x n, where each element is a wall, floor, or a box.
Your task is move the box 'B' to the target position 'T' under the following rules:
Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empy cell).
Floor is represented by character '.' that means free cell to walk.
Wall is represented by character '#' that means obstacle  (impossible to walk there). 
There is only one box 'B' and one target cell 'T' in the grid.
The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
The player cannot walk through the box.
Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.
Example 1:
Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.
Example 2:
Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1
Example 3:
Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.
Example 4:
Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1
Constraints:
m == grid.length
n == grid[i].length
1 <= m <= 20
1 <= n <= 20
grid contains only characters '.', '#',  'S' , 'T', or 'B'.
There is only one character 'S', 'B' and 'T' in the grid.
from collections import deque

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        m, n = len(grid), len(grid[0])
        
        def Can(i, j):
            ss.add((i, j))
            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                if 0 <= x < m and 0 <= y < n and (x, y) not in ss and grid[x][y] == '.':
                    Can(x, y)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    ppl = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'B':
                    box = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    target = (i, j)
                    grid[i][j] = '.'
        
        visited = set()
        queue = deque()
        queue.append((box[0], box[1], 0, ppl[0], ppl[1]))
        ss = set()
        
        while queue:
            x, y, count, p1, p2 = queue.popleft()
            if (x, y) == target:
                return count
            ss = {(x, y)}
            Can(p1, p2)
            
            if x+1 < m and 0 <= x-1 and grid[x+1][y] == '.' and grid[x-1][y] == '.':
                if (x-1, y, x, y) not in visited and (x-1, y) in ss:
                    visited.add((x-1, y, x, y))
                    queue.append( (x+1, y, count+1, x-1, y) )
                if (x+1, y, x, y) not in visited and (x+1, y) in ss:
                    visited.add((x+1, y, x, y))
                    queue.append( (x-1, y, count+1, x+1, y) )
            
            if y+1 < n and 0 <= y-1 and grid[x][y-1] == '.' and grid[x][y+1] == '.':
                #print(\"{}.{}\".format(x, y))
                if (x, y-1, x, y) not in visited and (x, y-1) in ss:
                    visited.add((x, y-1, x, y))
                    queue.append( (x, y+1, count+1, x, y-1) )
                if (x, y+1, x, y) not in visited and (x, y+1) in ss:
                    visited.add((x, y+1, x, y))
                    queue.append( (x, y-1, count+1, x, y+1) )
            
        return -1
            

from collections import deque

class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        
        m, n = len(grid), len(grid[0])
        
        def Can(i, j):
            ss.add((i, j))
            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                if 0 <= x < m and 0 <= y < n and (x, y) not in ss and grid[x][y] == '.':
                    Can(x, y)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    ppl = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'B':
                    box = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'T':
                    target = (i, j)
                    grid[i][j] = '.'
        
        visited = set()
        queue = deque()
        queue.append((box[0], box[1], 0, ppl[0], ppl[1]))
        ss = set()
        
        while queue:
            x, y, count, p1, p2 = queue.popleft()
            if (x, y) == target:
                return count
            ss = {(x, y)}
            Can(p1, p2)
            
            if x+1 < m and 0 <= x-1 and grid[x+1][y] == '.' and grid[x-1][y] == '.':
                if (x-1, y, x, y) not in visited and (x-1, y) in ss:
                    visited.add((x-1, y, x, y))
                    queue.append( (x+1, y, count+1, x-1, y) )
                if (x+1, y, x, y) not in visited and (x+1, y) in ss:
                    visited.add((x+1, y, x, y))
                    queue.append( (x-1, y, count+1, x+1, y) )
            
            if y+1 < n and 0 <= y-1 and grid[x][y-1] == '.' and grid[x][y+1] == '.':
                #print(\"{}.{}\".format(x, y))
                if (x, y-1, x, y) not in visited and (x, y-1) in ss:
                    visited.add((x, y-1, x, y))
                    queue.append( (x, y+1, count+1, x, y-1) )
                if (x, y+1, x, y) not in visited and (x, y+1) in ss:
                    visited.add((x, y+1, x, y))
                    queue.append( (x, y-1, count+1, x, y+1) )
            
        return -1
            
