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.

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal

Starter code: class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        

Solutions:
class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(m, n, g) = (len(grid), len(grid[0]), collections.defaultdict(list))
		for i in range(m):
			for j in range(n):
				g[grid[i][j]] += [complex(i, j)]

		def f(b, s):
			nonlocal time
			time += 1
			boxToTarget = b - target
			return (abs(boxToTarget.real) + abs(boxToTarget.imag) + s, abs(boxToTarget), time)
		(player, box, target, time) = (*g['S'], *g['B'], *g['T'], 1)
		floor = {player, box, target, *g['.']}
		alpha = [(f(box, 1), 1, player, box)]
		(directions, visited) = ((1, -1, 1j, -1j), set())
		low = dict.fromkeys(floor, 0)
		dfn = low.copy()
		count = 0
		index = {}

		def tarjan(currIndex, parentIndex):
			nonlocal count
			count += 1
			dfn[currIndex] = low[currIndex] = count
			index[count] = currIndex
			for direction in directions:
				nextIndex = currIndex + direction
				if nextIndex in floor and nextIndex != parentIndex:
					if not low[nextIndex]:
						tarjan(nextIndex, currIndex)
					low[currIndex] = min(low[currIndex], low[nextIndex])
		tarjan(box, -1)
		for currIndex in floor:
			connect = [currIndex]
			while dfn[connect[-1]] != low[connect[-1]]:
				connect.append(index[low[connect[-1]]])
			for w in connect[:-2]:
				low[w] = low[connect[-1]]
		if not low[player] * low[target]:
			return -1
		while alpha:
			(_, steps, currPlayer, currBox) = heapq.heappop(alpha)
			for direction in directions:
				(nextPlayer, nextBox) = (currBox - direction, currBox + direction)
				if nextBox in floor and nextPlayer in floor and ((nextPlayer, currBox) not in visited) and (low[currPlayer] == low[nextPlayer]):
					if nextBox == target:
						return steps
					heapq.heappush(alpha, (f(nextBox, steps + 1), steps + 1, currBox, nextBox))
					visited.add((nextPlayer, currBox))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		num_rows = len(grid)
		num_cols = len(grid[0])
		for r in range(num_rows):
			for c in range(num_cols):
				if grid[r][c] == 'T':
					(target_row, target_col) = (r, c)
					grid[r][c] = '.'
				elif grid[r][c] in 'B':
					(box_row, box_col) = (r, c)
					grid[r][c] = '.'
				elif grid[r][c] in 'S':
					(src_row, src_col) = (r, c)
					grid[r][c] = '.'

		def traversal(player_row, player_col, box_row, box_col, visited):
			if not (0 <= player_row < num_rows and 0 <= player_col < num_cols):
				return visited
			if grid[player_row][player_col] != '.' or (player_row, player_col) in visited:
				return visited
			visited.add((player_row, player_col))
			for (i, j) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				new_player_row = player_row + i
				new_player_col = player_col + j
				if new_player_row != box_row or new_player_col != box_col:
					traversal(new_player_row, new_player_col, box_row, box_col, visited)
			return visited
		queue = deque([(src_row, src_col, box_row, box_col, 0)])
		visited = {(src_row, src_col, box_row, box_col)}
		while queue:
			(curr_row, curr_col, box_row, box_col, num_pushs) = queue.popleft()
			reachable = traversal(curr_row, curr_col, box_row, box_col, set())
			for (i, j) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				new_box_row = box_row + i
				new_box_col = box_col + j
				if not (0 <= new_box_row < num_rows and 0 <= new_box_col < num_cols):
					continue
				if grid[new_box_row][new_box_col] != '.':
					continue
				if (box_row - i, box_col - j) in reachable and (box_row, box_col, new_box_row, new_box_col) not in visited:
					visited.add((box_row, box_col, new_box_row, new_box_col))
					if new_box_row == target_row and new_box_col == target_col:
						return num_pushs + 1
					queue.append((box_row, box_col, new_box_row, new_box_col, num_pushs + 1))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		queue = deque()
		m = len(grid)
		n = len(grid[0])
		visited = {}
		rq = deque()
		reach = {}
		(startx, starty) = (-1, -1)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'S':
					rq.append([i, j])
					(startx, starty) = (i, j)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'B':
					queue.append([i, j, 0, startx, starty])
					visited[i, j, startx, starty] = 1
		while len(queue) > 0:
			(x, y, step, startx, starty) = queue.popleft()
			if grid[x][y] == 'T':
				return step
			rq = deque()
			reach = {}
			rq.append([startx, starty])
			while len(rq) > 0:
				(rx, ry) = rq.popleft()
				reach[rx, ry] = 1
				for (deltax, deltay) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
					(nx, ny) = (rx + deltax, ry + deltay)
					if nx >= 0 and nx < m and (ny >= 0) and (ny < n):
						if grid[nx][ny] != '#' and (nx, ny) != (x, y) and ((nx, ny) not in reach):
							rq.append([nx, ny])
							reach[nx, ny] = 1
			for (deltax, deltay) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
				(nx, ny) = (x + deltax, y + deltay)
				(otherx, othery) = (x - deltax, y - deltay)
				if nx >= 0 and nx < m and (ny >= 0) and (ny < n) and (otherx >= 0) and (otherx < m) and (othery >= 0) and (othery < n):
					if grid[nx][ny] != '#' and grid[otherx][othery] != '#':
						if (nx, ny, otherx, othery) not in visited and (otherx, othery) in reach:
							queue.append([nx, ny, step + 1, otherx, othery])
							visited[nx, ny, otherx, othery] = 1
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(rows, cols) = (len(grid), len(grid[0]))
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] == 'T':
					target = (r, c)
				if grid[r][c] == 'S':
					start_person = (r, c)
				if grid[r][c] == 'B':
					start_box = (r, c)

		def heuristic(box):
			return abs(target[0] - box[0]) + abs(target[1] - box[1])

		def out_bounds(location):
			(r, c) = location
			return r < 0 or r >= rows or c < 0 or (c >= cols) or (grid[r][c] == '#')
		heap = [[heuristic(start_box), 0, start_person, start_box]]
		vis = set()
		while heap:
			(_, moves, person, box) = heapq.heappop(heap)
			if box == target:
				return moves
			if (person, box) in vis:
				continue
			vis.add((person, box))
			for (dr, dc) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
				new_person = (person[0] + dr, person[1] + dc)
				if out_bounds(new_person):
					continue
				if new_person == box:
					new_box = (box[0] + dr, box[1] + dc)
					if out_bounds(new_box):
						continue
					heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])
				else:
					heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box])
		return -1


from queue import deque

class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:

		def isValid(pos):
			(i, j) = (pos[0], pos[1])
			return 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] != '#')
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'T':
					target = (i, j)
				elif grid[i][j] == 'B':
					box = (i, j)
				elif grid[i][j] == 'S':
					player = (i, j)

		def personCanMove(pos, dest, box):
			que = deque([pos])
			seen = {pos}
			while que:
				p = que.popleft()
				if p == dest:
					return True
				(i, j) = (p[0], p[1])
				nextPos = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
				for (nextI, nextJ) in nextPos:
					if isValid((nextI, nextJ)) and (nextI, nextJ) not in seen and ((nextI, nextJ) != box):
						seen.add((nextI, nextJ))
						que.append((nextI, nextJ))
			return False
		q = deque([(box, player, 0)])
		seen = {box + player}
		while q:
			(b, p, pushes) = q.popleft()
			if b == target:
				return pushes
			nextBArr = [(b[0] - 1, b[1]), (b[0] + 1, b[1]), (b[0], b[1] + 1), (b[0], b[1] - 1)]
			pushPosArr = [(b[0] + 1, b[1]), (b[0] - 1, b[1]), (b[0], b[1] - 1), (b[0], b[1] + 1)]
			for (nextB, pushPos) in zip(nextBArr, pushPosArr):
				if isValid(nextB) and nextB + b not in seen:
					if isValid(pushPos) and personCanMove(p, pushPos, b):
						q.append((nextB, b, pushes + 1))
						seen.add(nextB + b)
		return -1


from collections import deque
directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]

def can_move(source, dest, a, walls, box):
	q = deque()
	q.append(source)
	visited = set()
	while q:
		item = q.popleft()
		if item == dest:
			return True
		if item in visited:
			continue
		visited.add(item)
		for direction in directions:
			new_item = (item[0] + direction[0], item[1] + direction[1])
			if is_valid(a, new_item, walls, box):
				q.append(new_item)

def is_valid(a, pos, walls, box=''):
	(x, y) = pos
	if 0 <= x < len(a) and 0 <= y < len(a[0]) and ((x, y) not in walls) and ((x, y) != box):
		return True
	return False

def get_info(a):
	walls = set()
	for i in range(len(a)):
		for j in range(len(a[0])):
			if a[i][j] == '#':
				walls.add((i, j))
			if a[i][j] == 'S':
				person = (i, j)
			if a[i][j] == 'T':
				target = (i, j)
			if a[i][j] == 'B':
				box = (i, j)
	return (person, target, box, walls)

def get_min_moves(a):
	(person, target, box, walls) = get_info(a)
	q = deque()
	q.append((0, box, person))
	result = float('inf')
	visited = set()
	while q:
		(dist, box, person) = q.popleft()
		if (box, person) in visited:
			continue
		visited.add((box, person))
		if box == target:
			result = min(result, dist)
			continue
		for direction in directions:
			new_player_position = (box[0] + direction[0], box[1] + direction[1])
			new_box = (box[0] + direction[0] * -1, box[1] + direction[1] * -1)
			if is_valid(a, new_box, walls) and can_move(person, new_player_position, a, walls, box):
				if is_valid(a, new_player_position, walls):
					q.append((dist + 1, new_box, box))
	return result if result != float('inf') else -1

class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		return get_min_moves(grid)


import heapq

class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		(xb, yb, xs, ys, xt, yt) = (-1, -1, -1, -1, -1, -1)
		for x in range(m):
			for y in range(n):
				if grid[x][y] == 'B':
					(xb, yb) = (x, y)
					grid[x][y] = '.'
				if grid[x][y] == 'S':
					(xs, ys) = (x, y)
					grid[x][y] = '.'
				if grid[x][y] == 'T':
					(xt, yt) = (x, y)
					grid[x][y] = '.'
		(q, seen) = ([(abs(xb - xt) + abs(yb - yt) + 0, 0, xb, yb, xs, ys)], set())
		while q:
			(h, d, xb, yb, xs, ys) = heapq.heappop(q)
			if (xb, yb) == (xt, yt):
				return d
			if (xb, yb, xs, ys) not in seen:
				seen.add((xb, yb, xs, ys))
				for (dx, dy) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
					(xr, yr) = (xs + dx, ys + dy)
					if 0 <= xr < m and 0 <= yr < n and (grid[xr][yr] == '.'):
						if (xr, yr) == (xb, yb):
							(xc, yc) = (xb + dx, yb + dy)
							if 0 <= xc < m and 0 <= yc < n and (grid[xc][yc] == '.'):
								heapq.heappush(q, (abs(xc - xt) + abs(yc - yt) + d + 1, d + 1, xc, yc, xr, yr))
						else:
							heapq.heappush(q, (h, d, xb, yb, xr, yr))
		return -1


from collections import deque

class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:

		def can_reach(x, y):
			q = deque([x])
			seen = set([x])
			while q:
				(i, j) = q.popleft()
				if (i, j) == y:
					return True
				for (di, dj) in ((-1, 0), (1, 0), (0, 1), (0, -1)):
					i_ = i + di
					j_ = j + dj
					if 0 <= i_ < m and 0 <= j_ < n and ((i_, j_) not in seen) and (grid[i_][j_] == '.'):
						seen.add((i_, j_))
						q.append((i_, j_))
			return False
		(m, n) = (len(grid), len(grid[0]))
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'T':
					t = (i, j)
					grid[i][j] = '.'
				if grid[i][j] == 'B':
					b = (i, j)
					grid[i][j] = '.'
				if grid[i][j] == 'S':
					s = (i, j)
					grid[i][j] = '.'
		depth = 0
		q = deque([(b, s)])
		seen = set([(b, s)])
		while q:
			depth += 1
			for _ in range(len(q)):
				(b, s) = q.popleft()
				grid[b[0]][b[1]] = 'B'
				for (dx, dy) in ((-1, 0), (1, 0), (0, 1), (0, -1)):
					(x, y) = (b[0] + dx, b[1] + dy)
					(bx, by) = (b[0] - dx, b[1] - dy)
					if 0 <= x < m and 0 <= y < n and (0 <= bx < m) and (0 <= by < n) and (grid[x][y] != '#') and (grid[bx][by] != '#') and can_reach(s, (x, y)) and (((bx, by), b) not in seen):
						seen.add(((bx, by), b))
						q.append(((bx, by), b))
						if (bx, by) == t:
							return depth
				grid[b[0]][b[1]] = '.'
		return -1


class Solution:

	def minPushBox(self, grid) -> int:
		from collections import deque
		(r, c) = (len(grid), len(grid[0]))
		di = [[0, 1], [0, -1], [1, 0], [-1, 0]]

		def bfs(sx, sy, ex, ey, path):
			t = deque()
			s = set()
			s.add(str((sx, sy)))
			t.append([sx, sy])
			while t:
				(x, y) = t.popleft()
				if x == ex and y == ey:
					return True
				for (i, j) in di:
					ti = x + i
					tj = y + j
					if 0 <= ti < r and 0 <= tj < c and (path[ti][tj] == '.') and (str((ti, tj)) not in s):
						s.add(str((ti, tj)))
						t.append([ti, tj])
			return False
		bx = by = sx = sy = tx = ty = -1
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 'B':
					(bx, by) = (i, j)
					grid[i][j] = '.'
				if grid[i][j] == 'S':
					(sx, sy) = (i, j)
					grid[i][j] = '.'
				if grid[i][j] == 'T':
					(tx, ty) = (i, j)
					grid[i][j] = '.'
		if -1 in [bx, by, sx, sy, tx, ty]:
			return -1
		t = deque()
		s = set()
		t.append([bx, by, sx, sy, 0])
		s.add(str((bx, by, sx, sy)))
		while t:
			(bx, by, sx, sy, step) = t.popleft()
			if bx == tx and by == ty:
				return step
			grid[bx][by] = 'B'
			for (i, j) in di:
				ti = bx + i
				tj = by + j
				tii = bx - i
				tjj = by - j
				if 0 <= ti < r and 0 <= tj < c and (grid[ti][tj] == '.') and (str((ti, tj, bx, by)) not in s) and (0 <= tii < r) and (0 <= tjj < c) and (grid[tii][tjj] == '.') and bfs(sx, sy, tii, tjj, grid):
					t.append([ti, tj, bx, by, step + 1])
					s.add(str((ti, tj, bx, by)))
			grid[bx][by] = '.'
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def check(p1, p2, t1, t2, b1, b2):
			visited = visited = [[False for _ in range(n)] for _ in range(m)]
			queue = collections.deque()
			queue.append((p1, p2))
			visited[p1][p2] = True
			while queue:
				(x, y) = queue.popleft()
				if (x, y) == (t1, t2):
					return True
				for (dx, dy) in moves:
					(nx, ny) = (x + dx, y + dy)
					if 0 <= nx < m and 0 <= ny < n:
						if visited[nx][ny]:
							continue
						if (nx, ny) == (t1, t2):
							return True
						if (nx, ny) != (b1, b2) and grid[nx][ny] != '#':
							queue.append((nx, ny))
							visited[nx][ny] = True
			return False

		def inbound(x, y):
			return 0 <= x < m and 0 <= y < n
		for i in range(m):
			for j in range(n):
				if grid[i][j] != '#':
					if grid[i][j] == 'S':
						player = (i, j)
					elif grid[i][j] == 'B':
						box = (i, j)
					elif grid[i][j] == 'T':
						end = (i, j)
		(p1, p2) = player
		(b1, b2) = box
		(e1, e1) = end
		visited = set()
		step = -1
		queue = collections.deque()
		queue.append((b1, b2, p1, p2))
		while queue:
			step += 1
			for _ in range(len(queue)):
				(x, y, p1, p2) = queue.popleft()
				if inbound(x - 1, y) and inbound(x + 1, y) and (grid[x + 1][y] != '#') and check(p1, p2, x + 1, y, x, y):
					if (x - 1, y, x, y) not in visited:
						if grid[x - 1][y] != '#':
							if grid[x - 1][y] == 'T':
								return step + 1
							else:
								queue.append((x - 1, y, x, y))
								visited.add((x - 1, y, x, y))
								visited.add((x, y, x + 1, y))
				if inbound(x - 1, y) and inbound(x + 1, y) and (grid[x - 1][y] != '#') and check(p1, p2, x - 1, y, x, y):
					if (x + 1, y, x, y) not in visited:
						if grid[x + 1][y] != '#':
							if grid[x + 1][y] == 'T':
								return step + 1
							else:
								queue.append((x + 1, y, x, y))
								visited.add((x + 1, y, x, y))
								visited.add((x, y, x - 1, y))
				if inbound(x, y + 1) and inbound(x, y - 1) and (grid[x][y + 1] != '#') and check(p1, p2, x, y + 1, x, y):
					if (x, y - 1, x, y) not in visited:
						if grid[x][y - 1] != '#':
							if grid[x][y - 1] == 'T':
								return step + 1
							else:
								queue.append((x, y - 1, x, y))
								visited.add((x, y - 1, x, y))
								visited.add((x, y, x, y + 1))
				if inbound(x, y + 1) and inbound(x, y - 1) and (grid[x][y - 1] != '#') and check(p1, p2, x, y - 1, x, y):
					if (x, y + 1, x, y) not in visited:
						if grid[x][y + 1] != '#':
							if grid[x][y + 1] == 'T':
								return step + 1
							else:
								queue.append((x, y + 1, x, y))
								visited.add((x, y + 1, x, y))
								visited.add((x, y, x, y - 1))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		dirs = [(0, 1), (-1, 0), (1, 0), (0, -1)]
		(m, n) = (len(grid), len(grid[0]))

		def connected(s, e):
			q = collections.deque([s])
			visited = set([s])
			while q:
				(r, c) = q.popleft()
				if (r, c) == e:
					return True
				for (dr, dc) in dirs:
					(nr, nc) = (r + dr, c + dc)
					if 0 <= nr < m and 0 <= nc < n and (grid[nr][nc] == '.'):
						if (nr, nc) not in visited:
							visited.add((nr, nc))
							q.append((nr, nc))
			return False
		B = S = T = (0, 0)
		for r in range(m):
			for c in range(n):
				if grid[r][c] == 'B':
					B = (r, c)
					grid[r][c] = '.'
				elif grid[r][c] == 'S':
					S = (r, c)
					grid[r][c] = '.'
				elif grid[r][c] == 'T':
					T = (r, c)
					grid[r][c] = '.'
		ans = 0
		q = collections.deque([(B, S, 0)])
		visited = set([(B, S)])
		while q:
			((r, c), (rs, cs), step) = q.popleft()
			if (r, c) == T:
				return step
			for (dr, dc) in dirs:
				(nr, nc) = (r + dr, c + dc)
				(pr, pc) = (r - dr, c - dc)
				if 0 <= nr < m and 0 <= nc < n and (grid[nr][nc] == '.') and (((nr, nc), (r, c)) not in visited):
					grid[r][c] = 'B'
					if 0 <= pr < m and 0 <= pc < n and (grid[pr][pc] == '.') and connected((pr, pc), (rs, cs)):
						visited.add(((nr, nc), (r, c)))
						q.append(((nr, nc), (r, c), step + 1))
					grid[r][c] = '.'
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def is_floor(i, j):
			return 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] != '#')

		def bfs(start_i, start_j, box_i, box_j):
			(visited, queue, reach_list) = ([[0 for _ in range(n)] for _ in range(m)], [(start_i, start_j)], [])
			visited[start_i][start_j] = 1
			reach_list_upbound = len([1 for (delta_i, delta_j) in [(0, -1), (-1, 0), (0, 1), (1, 0)] if is_floor(box_i + delta_i, box_j + delta_j)])
			while queue:
				(start_i, start_j) = queue.pop(0)
				for (delta_i, delta_j) in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
					if start_i + delta_i == box_i and start_j + delta_j == box_j:
						reach_list.append((delta_i, delta_j))
						if len(reach_list) >= reach_list_upbound:
							return reach_list
					elif is_floor(start_i + delta_i, start_j + delta_j) and visited[start_i + delta_i][start_j + delta_j] == 0:
						visited[start_i + delta_i][start_j + delta_j] = 1
						queue.append((start_i + delta_i, start_j + delta_j))
			return reach_list
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'S':
					source = (i, j)
				elif grid[i][j] == 'B':
					box = (i, j)
				elif grid[i][j] == 'T':
					target = (i, j)
		queue = [(source, box, 0)]
		visited = set()
		while queue:
			(source, box, depth) = queue.pop(0)
			if box[0] == target[0] and box[1] == target[1]:
				return depth
			reach_list = bfs(source[0], source[1], box[0], box[1])
			for mov in reach_list:
				(s, b) = ((box[0], box[1]), (box[0] + mov[0], box[1] + mov[1]))
				if is_floor(b[0], b[1]) and (s, b) not in visited:
					visited.add((s, b))
					queue.append((s, b, depth + 1))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:

		def player_moves(box_i, box_j, p_i, p_j):
			res = []
			if p_i > 0 and grid[p_i - 1][p_j] != '#' and ((p_i - 1, p_j) != (box_i, box_j)):
				res.append((p_i - 1, p_j))
			if p_i < len(grid) - 1 and grid[p_i + 1][p_j] != '#' and ((p_i + 1, p_j) != (box_i, box_j)):
				res.append((p_i + 1, p_j))
			if p_j > 0 and grid[p_i][p_j - 1] != '#' and ((p_i, p_j - 1) != (box_i, box_j)):
				res.append((p_i, p_j - 1))
			if p_j < len(grid[0]) - 1 and grid[p_i][p_j + 1] != '#' and ((p_i, p_j + 1) != (box_i, box_j)):
				res.append((p_i, p_j + 1))
			return res

		def is_accessible(cell_i, cell_j, box_i, box_j, p_i, p_j):
			if grid[cell_i][cell_j] == '#':
				return False
			q = deque()
			visited = set()
			q.append((p_i, p_j))
			visited.add((p_i, p_j))
			while q:
				size = len(q)
				for i in range(size):
					pop = q.popleft()
					if pop == (cell_i, cell_j):
						return True
					for nex in player_moves(box_i, box_j, pop[0], pop[1]):
						if nex not in visited:
							q.append(nex)
							visited.add(nex)
			return False

		def box_moves(state):
			res = set()
			(box_i, box_j, p_i, p_j) = (state[0], state[1], state[2], state[3])
			if box_i > 0 and is_accessible(box_i - 1, box_j, box_i, box_j, p_i, p_j) and (box_i + 1 < len(grid)) and (grid[box_i + 1][box_j] != '#'):
				res.add((box_i + 1, box_j, box_i, box_j))
			if box_i < len(grid) - 1 and is_accessible(box_i + 1, box_j, box_i, box_j, p_i, p_j) and (box_i - 1 >= 0) and (grid[box_i - 1][box_j] != '#'):
				res.add((box_i - 1, box_j, box_i, box_j))
			if box_j > 0 and is_accessible(box_i, box_j - 1, box_i, box_j, p_i, p_j) and (box_j + 1 < len(grid[0])) and (grid[box_i][box_j + 1] != '#'):
				res.add((box_i, box_j + 1, box_i, box_j))
			if box_j < len(grid[0]) - 1 and is_accessible(box_i, box_j + 1, box_i, box_j, p_i, p_j) and (box_j - 1 >= 0) and (grid[box_i][box_j - 1] != '#'):
				res.add((box_i, box_j - 1, box_i, box_j))
			return res

		def start_state():
			(box_i, box_j, p_i, p_j) = (-1, -1, -1, -1)
			for i in range(len(grid)):
				for j in range(len(grid[0])):
					if grid[i][j] == 'B':
						(box_i, box_j) = (i, j)
					elif grid[i][j] == 'S':
						(p_i, p_j) = (i, j)
			return (box_i, box_j, p_i, p_j)
		q = deque()
		visited = set()
		start = start_state()
		q.append(start)
		visited.add(start)
		moves = -1
		while q:
			size = len(q)
			moves += 1
			for i in range(size):
				pop = q.popleft()
				if grid[pop[0]][pop[1]] == 'T':
					return moves
				for nx in box_moves(pop):
					if nx not in visited:
						q.append(nx)
						visited.add(nx)
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		(R, C) = (len(grid), len(grid[0]))
		b_pos = s_pos = t_pos = None
		for r in range(R):
			for c in range(C):
				if grid[r][c] == 'B':
					b_pos = (r, c)
				if grid[r][c] == 'S':
					s_pos = (r, c)
				if grid[r][c] == 'T':
					t_pos = (r, c)

		def is_empty(r, c):
			return 0 <= r < R and 0 <= c < C and (grid[r][c] != '#')

		@lru_cache(None)
		def can_reach(r1, c1, r2, c2, br, bc):
			if not is_empty(r2, c2):
				return False
			q = [(r1, c1)]
			used = set()
			for (r, c) in q:
				if (r, c) in used or (r, c) == (br, bc):
					continue
				used.add((r, c))
				if (r, c) == (r2, c2):
					return True
				for (dr, dc) in dirs:
					(nr, nc) = (dr + r, dc + c)
					if is_empty(nr, nc):
						q.append((nr, nc))
			return False
		visited = set()
		pq = [(0, b_pos, s_pos)]
		while pq:
			(steps, b_pos, s_pos) = heappop(pq)
			if (b_pos, s_pos) in visited:
				continue
			visited.add((b_pos, s_pos))
			if b_pos == t_pos:
				return steps
			(sr, sc) = s_pos
			(br, bc) = b_pos
			for (dr, dc) in dirs:
				(br1, bc1) = (br + dr, bc + dc)
				(br2, bc2) = (br - dr, bc - dc)
				if is_empty(br2, bc2) and can_reach(sr, sc, br1, bc1, br, bc):
					heappush(pq, (steps + 1, (br2, bc2), b_pos))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(M, N) = (len(grid), len(grid[0]))
		for i in range(M):
			for j in range(N):
				if grid[i][j] in ['#', '.']:
					continue
				if grid[i][j] == 'S':
					player = (i, j)
				elif grid[i][j] == 'B':
					box = (i, j)
				else:
					target = (i, j)

		def heuristic(box):
			return abs(target[0] - box[0]) + abs(target[1] - box[1])

		@functools.lru_cache(None)
		def reach(player, pos, box):
			(i, j) = pos
			if not (0 <= i < M and 0 <= j < N and (grid[i][j] != '#')):
				return False
			hp = [player]
			seen = set([player])
			while hp:
				player = heapq.heappop(hp)
				if player == pos:
					return True
				(p0, p1) = player
				for (i, j) in [(p0 - 1, p1), (p0 + 1, p1), (p0, p1 - 1), (p0, p1 + 1)]:
					if 0 <= i < M and 0 <= j < N and (grid[i][j] != '#') and ((i, j) != box) and ((i, j) not in seen):
						seen.add((i, j))
						heapq.heappush(hp, (i, j))
			return False
		seen = set([(box, player)])
		hp = [(heuristic(box), 0, box, player)]
		while hp:
			(_, step, box, player) = heapq.heappop(hp)
			print(box)
			if box == target:
				return step
			(b0, b1) = box
			for (i, j) in [(b0 - 1, b1), (b0 + 1, b1), (b0, b1 - 1), (b0, b1 + 1)]:
				if 0 <= i < M and 0 <= j < N and (grid[i][j] != '#') and (((i, j), player) not in seen) and reach(player, (b0 * 2 - i, b1 * 2 - j), box):
					seen.add(((i, j), player))
					heapq.heappush(hp, (heuristic((i, j)) + step + 1, step + 1, (i, j), box))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(R, C) = (len(grid), len(grid[0]))

		def neighbor(r, c):
			for (nr, nc) in [[r + 1, c], [r, c + 1], [r - 1, c], [r, c - 1]]:
				if 0 <= nr < R and 0 <= nc < C and (grid[nr][nc] != '#'):
					yield (nr, nc)

		def can_reach(worker, target, box):
			if worker == target:
				return True
			if target[0] >= R or target[0] < 0 or target[1] >= C or (target[1] < 0) or (grid[target[0]][target[1]] == '#'):
				return False
			start = [worker]
			end = [target]
			start_seen = {worker}
			end_seen = {target}
			while start and end:
				n_start = []
				for node in start:
					(r, c) = node
					for (nr, nc) in neighbor(r, c):
						if (nr, nc) in end_seen:
							return True
						if (nr, nc) != box and (nr, nc) not in start_seen:
							start_seen.add((nr, nc))
							n_start.append((nr, nc))
				n_end = []
				for node in end:
					(r, c) = node
					for (nr, nc) in neighbor(r, c):
						if (nr, nc) in start_seen:
							return True
						if (nr, nc) != box and (nr, nc) not in end_seen:
							end_seen.add((nr, nc))
							n_end.append((nr, nc))
				start = n_start
				end = n_end
		(S, B, T) = (None, None, None)
		for r in range(R):
			for c in range(C):
				if grid[r][c] == 'S':
					S = (r, c)
				elif grid[r][c] == 'B':
					B = (r, c)
				elif grid[r][c] == 'T':
					T = (r, c)
		level = [(S, B)]
		seen = {(S, B)}
		steps = 0
		while level:
			n_level = []
			for (player, box) in level:
				(r, c) = box
				for (nr, nc) in neighbor(r, c):
					(opp_r, opp_c) = (2 * r - nr, 2 * c - nc)
					if can_reach(player, (opp_r, opp_c), box):
						if (nr, nc) == T:
							return steps + 1
						n_state = (box, (nr, nc))
						if n_state not in seen:
							seen.add(n_state)
							n_level.append(n_state)
			level = n_level
			steps += 1
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'B':
					(bi, bj) = (i, j)
					grid[i][j] = '.'
				elif grid[i][j] == 'S':
					(si, sj) = (i, j)
					grid[i][j] = '.'
				elif grid[i][j] == 'T':
					(ti, tj) = (i, j)
					grid[i][j] = '.'
		q = [(bi, bj, si, sj, 0)]
		seen = {(bi, bj, si, sj)}
		while q:
			(bi, bj, si, sj, dist) = q.pop(0)
			if (bi, bj) == (ti, tj):
				return dist
			for (dx, dy) in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
				(si_new, sj_new) = (bi + dx, bj + dy)
				(bi_new, bj_new) = (bi - dx, bj - dy)
				if (bi_new, bj_new, bi, bj) not in seen and self.canMoveTo(grid, bi, bj, si, sj, si_new, sj_new) and (0 <= bi_new < m) and (0 <= bj_new < n) and (grid[bi_new][bj_new] == '.'):
					q.append((bi_new, bj_new, bi, bj, dist + 1))
					seen.add((bi_new, bj_new, bi, bj))
		return -1

	def canMoveTo(self, grid, bi, bj, si, sj, si_new, sj_new):
		(m, n) = (len(grid), len(grid[0]))
		q = [(si, sj)]
		visited = {(si, sj)}
		while q:
			(si, sj) = q.pop(0)
			if si == si_new and sj == sj_new:
				return True
			for (dx, dy) in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
				(i, j) = (si + dx, sj + dy)
				if (i, j) not in visited and 0 <= i < m and (0 <= j < n) and ((i, j) != (bi, bj)) and (grid[i][j] != '#'):
					q.append((i, j))
					visited.add((i, j))
		return False


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		self.empty = [['.' for _ in range(n)] for _ in range(m)]
		for (i, row) in enumerate(grid):
			for (j, c) in enumerate(row):
				if c == 'B':
					start = (i, j)
				if c == 'S':
					player = (i, j)
				if c == 'T':
					target = (i, j)
				if c == '#':
					self.empty[i][j] = '#'
		visit = [[0 for _ in range(n)] for _ in range(m)]
		visit[start[0]][start[1]] += 1
		deq = collections.deque([(start, player, (-1, -1))])
		push = 0
		paths = dict()
		while deq and push < m * n:
			sz = len(deq)
			for i in range(sz):
				(box, player, previous) = deq.popleft()
				if box == target:
					return push
				cango = paths[player, box] if (player, box) in paths else self.player(player, box, self.empty)
				paths[player, box] = cango
				for d in self.direction:
					(nr, nc) = (box[0] + d[0], box[1] + d[1])
					(pr, pc) = (box[0] + d[2], box[1] + d[3])
					if 0 <= nr < m and 0 <= nc < n and (0 <= pr < m) and (0 <= pc < n):
						if self.empty[nr][nc] == '.' and cango[pr][pc] and (visit[nr][nc] < 2):
							visit[nr][nc] += 1
							deq.append(((nr, nc), (pr, pc), box))
			push += 1
		return -1

	def player(self, player, box, grid):
		(m, n) = (len(grid), len(grid[0]))
		visit = [[False for _ in range(n)] for _ in range(m)]
		visit[player[0]][player[1]] = True
		deq = collections.deque([player])
		while deq:
			sz = len(deq)
			for i in range(sz):
				cur = deq.popleft()
				for d in self.direction:
					(nr, nc) = (cur[0] + d[0], cur[1] + d[1])
					if 0 <= nr < m and 0 <= nc < n and (grid[nr][nc] == '.') and (not visit[nr][nc]) and (box != (nr, nc)):
						visit[nr][nc] = True
						deq.append((nr, nc))
		return visit

	def __init__(self):
		self.direction = ((0, 1, 0, -1), (0, -1, 0, 1), (1, 0, -1, 0), (-1, 0, 1, 0))
		self.empty = None


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(R, C) = (len(grid), len(grid[0]))

		def nxt(pos):
			(r, c) = pos
			res = []
			for (nr, nc) in [[r + 1, c], [r, c + 1], [r - 1, c], [r, c - 1]]:
				if 0 <= nr < R and 0 <= nc < C and (grid[nr][nc] != '#'):
					res.append((nr, nc))
			return res

		def connected(p, q, box):
			queue = collections.deque([p])
			seen = set()
			while queue:
				node = queue.popleft()
				for (nr, nc) in nxt(node):
					if (nr, nc) != box:
						if (nr, nc) == q:
							return True
						if (nr, nc) not in seen:
							seen.add((nr, nc))
							queue.append((nr, nc))
			return False
		(target, box, worker) = (None, None, None)
		for r in range(R):
			for c in range(C):
				if grid[r][c] == 'S':
					worker = (r, c)
				if grid[r][c] == 'B':
					box = (r, c)
				if grid[r][c] == 'T':
					target = (r, c)
		level = []
		seen = set()
		for pos in nxt(box):
			if connected(pos, worker, box):
				level.append((box, pos))
				seen.add((box, pos))
		grid[box[0]][box[1]] = '.'
		steps = 0
		while level:
			n_level = []
			for (b, w) in level:
				candi = nxt(b)
				for pos in candi:
					nb = (2 * b[0] - pos[0], 2 * b[1] - pos[1])
					if nb == target:
						return steps + 1
					if nb in candi and (nb, b) not in seen and connected(w, pos, b):
						seen.add((nb, b))
						n_level.append((nb, b))
			steps += 1
			level = n_level
		return -1


class Solution:

	def minPushBox(self, grid) -> int:
		T = B = S = (-1, -1)
		l = len(grid)
		w = len(grid[0])
		for i in range(l):
			for j in range(w):
				if grid[i][j] == 'T':
					T = (i, j)
				elif grid[i][j] == 'B':
					B = (i, j)
				elif grid[i][j] == 'S':
					S = (i, j)
		directions = [0, -1, 0, 1, 0]
		q = [B + S]
		visited = set()
		steps = 0
		self.next_step = (-1, -1, -1, -1)

		def is_pushable(cur_bs, dx, dy):
			(bx, by, sx, sy) = cur_bs
			nbx = bx + dx
			nby = by + dy
			nsx = bx - dx
			nsy = by - dy
			if is_valid(nbx, nby) and is_valid(nsx, nsy):
				if is_reachable(sx, sy, nsx, nsy, bx, by):
					self.next_step = (nbx, nby, nsx, nsy)
					return True
			return False

		def is_valid(nx, ny):
			return 0 <= nx < l and 0 <= ny < w and (grid[nx][ny] != '#')

		def is_reachable(sx, sy, nsx, nsy, cur_bx, cur_by):
			queue = [(sx, sy)]
			visited_set = set()
			while queue:
				cur_s = queue.pop(0)
				if cur_s not in visited_set and cur_s != (cur_bx, cur_by):
					visited_set.add(cur_s)
					if cur_s == (nsx, nsy):
						return True
					(cx, cy) = cur_s
					for idx in range(4):
						(dx, dy) = (directions[idx], directions[idx + 1])
						(nx, ny) = (cx + dx, cy + dy)
						if is_valid(nx, ny):
							queue.append((nx, ny))
			return False
		while q:
			tmp = []
			for cur in q:
				if cur not in visited:
					visited.add(cur)
					for i in range(4):
						(dir_x, dir_y) = (directions[i], directions[i + 1])
						if is_pushable(cur, dir_x, dir_y):
							(box_x, box_y, _, _) = self.next_step
							if (box_x, box_y) == T:
								return steps + 1
							tmp.append(self.next_step)
			q = tmp
			steps += 1
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(rows, cols) = (len(grid), len(grid[0]))
		(br, bc) = (-1, -1)
		(sr, sc) = (-1, -1)
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] == 'B':
					(br, bc) = (r, c)
				elif grid[r][c] == 'S':
					(sr, sc) = (r, c)

		def reachable(br, bc, sr, sc, tr, tc):
			visited = {(sr, sc)}

			def helper(curr, curc):
				if curr == tr and curc == tc:
					return True
				for (dr, dc) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					(newr, newc) = (curr + dr, curc + dc)
					if newr < 0 or newr >= rows or newc < 0 or (newc >= cols):
						continue
					if grid[newr][newc] == '#' or (newr, newc) == (br, bc):
						continue
					if (newr, newc) in visited:
						continue
					visited.add((newr, newc))
					if helper(newr, newc):
						return True
				return False
			return helper(sr, sc)
		seen = {(br, bc, sr, sc)}
		step = 0
		frontier = [(br, bc, sr, sc)]
		while frontier:
			newft = []
			for (br, bc, sr, sc) in frontier:
				if grid[br][bc] == 'T':
					return step
				for (dr, dc) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					(newr, newc) = (br + dr, bc + dc)
					if newr < 0 or newr >= rows or newc < 0 or (newc >= cols):
						continue
					if grid[newr][newc] == '#':
						continue
					(targr, targc) = (br - dr, bc - dc)
					if targr < 0 or targr >= rows or targc < 0 or (targc >= cols):
						continue
					if grid[targr][targc] == '#':
						continue
					if (newr, newc, targr, targc) in seen:
						continue
					if not reachable(br, bc, sr, sc, targr, targc):
						continue
					seen.add((newr, newc, targr, targc))
					newft.append((newr, newc, targr, targc))
			step += 1
			frontier = newft
		return -1


import heapq

class Solution:

	def est_distance(self, grid, target_posi, box_posi, move):
		return move + abs(target_posi[0] - box_posi[0]) + abs(target_posi[1] - box_posi[1])

	def isvalid_posi(self, grid, m, n, posi):
		(i, j) = posi
		if i < 0 or i >= m or j < 0 or (j >= n):
			return False
		return grid[i][j] != '#'

	def minPushBox(self, grid: List[List[str]]) -> int:
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'B':
					box_posi = (i, j)
				if grid[i][j] == 'T':
					target_posi = (i, j)
				if grid[i][j] == 'S':
					start_posi = (i, j)
		seen = set()
		seen.add((box_posi, start_posi))
		init_dist = self.est_distance(grid, target_posi, box_posi, 0)
		heap = [(init_dist, 0, box_posi, start_posi)]
		while heap:
			(dist, move, current_box, current_human) = heapq.heappop(heap)
			if current_box == target_posi:
				return move
			for (row_move, col_move) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
				new_human = (current_human[0] + row_move, current_human[1] + col_move)
				if not self.isvalid_posi(grid, m, n, new_human):
					continue
				if (current_box, new_human) not in seen:
					if new_human == current_box:
						new_box = (current_box[0] + row_move, current_box[1] + col_move)
						if self.isvalid_posi(grid, m, n, new_box):
							seen.add((new_box, new_human))
							new_dist = self.est_distance(grid, target_posi, new_box, move + 1)
							heapq.heappush(heap, (new_dist, move + 1, new_box, new_human))
					else:
						seen.add((current_box, new_human))
						new_dist = self.est_distance(grid, target_posi, current_box, move)
						heapq.heappush(heap, (new_dist, move, current_box, new_human))
		return -1


class Solution:

	def minPushBox(self, A: List[List[str]]) -> int:

		def reachable(sx, sy, tsx, tsy, bx, by, A, dirs):
			(m, n) = (len(A), len(A[0]))
			visited = [[0] * 20 for _ in range(20)]
			visited[sx][sy] = 1
			q = deque()
			q.append([sx, sy])
			while q:
				(sx, sy) = q.popleft()
				for (dx, dy) in dirs:
					(nsx, nsy) = (sx + dx, sy + dy)
					if 0 <= nsx < m and 0 <= nsy < n and (visited[nsx][nsy] == 0) and (A[nsx][nsy] in '.T' and [nsx, nsy] != [bx, by]):
						if [nsx, nsy] == [tsx, tsy]:
							return True
						visited[nsx][nsy] = 1
						q.append([nsx, nsy])
			return False
		(m, n) = (len(A), len(A[0]))
		for i in range(m):
			for j in range(n):
				if A[i][j] == 'B':
					(bx, by) = (i, j)
					A[i][j] = '.'
				if A[i][j] == 'S':
					(sx, sy) = (i, j)
					A[i][j] = '.'
		dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		visited = [[0] * 400 for _ in range(400)]
		visited[bx * 20 + by][sx * 20 + sy] = 1
		q = deque()
		q.append([bx, by, sx, sy, 0])
		while q:
			(bx, by, sx, sy, step) = q.popleft()
			for (dx, dy) in dirs:
				(nbx, nby) = (bx + dx, by + dy)
				if 0 <= nbx < m and 0 <= nby < n and (A[nbx][nby] in '.T'):
					(nsx, nsy) = (2 * bx - nbx, 2 * by - nby)
					if 0 <= nsx < m and 0 <= nsy < n and reachable(sx, sy, nsx, nsy, bx, by, A, dirs) and (visited[nbx * 20 + nby][nsx * 20 + nsy] == 0):
						if A[nbx][nby] == 'T':
							return step + 1
						visited[nbx * 20 + nby][nsx * 20 + nsy] = 1
						q.append([nbx, nby, nsx, nsy, step + 1])
		return -1


from heapq import heappush, heappop

class Solution:

	def minPushBox(self, A: List[List[str]]) -> int:
		(m, n) = (len(A), len(A[0]))
		for i in range(m):
			for j in range(n):
				if A[i][j] == 'B':
					b_pos = (i, j)
				elif A[i][j] == 'T':
					t_pos = (i, j)
				elif A[i][j] == 'S':
					p_pos = (i, j)

		def estimate(pos):
			return abs(t_pos[0] - pos[0]) + abs(t_pos[1] - pos[1])
		seen = {(p_pos, b_pos)}
		heap = [[estimate(b_pos), 0, p_pos, b_pos]]
		nbs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		while heap:
			(est, cost, person, box) = heappop(heap)
			if box == t_pos:
				return cost
			for (a, b) in nbs:
				(x, y) = (person[0] + a, person[1] + b)
				if 0 <= x < m and 0 <= y < n and (A[x][y] != '#'):
					n_person = (x, y)
					n_box = box
					n_cost = cost
					if n_person == box:
						n_box = (x + a, y + b)
						n_cost += 1
					if 0 <= n_box[0] < m and 0 <= n_box[1] < n and (A[n_box[0]][n_box[1]] != '#') and ((n_person, n_box) not in seen):
						heappush(heap, [estimate(n_box) + n_cost, n_cost, n_person, n_box])
						seen.add((n_person, n_box))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'T':
					t = (i, j)
				elif grid[i][j] == 'S':
					s = (i, j)
				elif grid[i][j] == 'B':
					b = (i, j)
		dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		q = [tuple(s + b)]
		seen = set(q)
		steps = 0
		while q:
			nq = []
			for (si, sj, bi, bj) in q:
				if t == (bi, bj):
					return steps
				for (di, dj) in dirs:
					(nsi, nsj) = (si + di, sj + dj)
					if nsi == bi and nsj == bj:
						(nbi, nbj) = (bi + di, bj + dj)
						ds = 1
					else:
						(nbi, nbj) = (bi, bj)
						ds = 0
					if not (0 <= nsi < n and 0 <= nsj < m):
						continue
					if not (0 <= nbi < n and 0 <= nbj < m):
						continue
					if grid[nsi][nsj] == '#' or grid[nbi][nbj] == '#':
						continue
					nsb = (nsi, nsj, nbi, nbj)
					if nsb in seen:
						continue
					seen.add(nsb)
					if ds == 0:
						q.append(nsb)
					else:
						nq.append(nsb)
			q = nq
			steps += 1
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		check = lambda i, j: 0 <= i < m and 0 <= j < n and (grid[i][j] != '#')
		dist = lambda i, j: abs(i - ti) + abs(j - tj)
		(m, n) = (len(grid), len(grid[0]))
		dij = [[0, -1], [0, 1], [-1, 0], [1, 0]]
		(pi, pj, bi, bj) = (0, 0, 0, 0)
		(ti, tj) = (0, 0)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'S':
					(pi, pj) = (i, j)
				if grid[i][j] == 'B':
					(bi, bj) = (i, j)
				if grid[i][j] == 'T':
					(ti, tj) = (i, j)
		for (i, j) in [[ti, tj], [bi, bj]]:
			k = 0
			for (di, dj) in dij:
				(ii, jj) = (i + di, j + dj)
				if not (0 <= ii < m and 0 <= jj < n) or grid[ii][jj] == '#':
					k += 1
			if k == 4:
				return -1
		q = [(0, pi, pj, bi, bj)]
		visited = {(pi, pj, bi, bj)}
		pushes = 1000000.0
		while q:
			(psh, pi, pj, bi, bj) = heapq.heappop(q)
			if grid[bi][bj] == 'T':
				return psh
			for (di, dj) in dij:
				(pii, pjj) = (pi + di, pj + dj)
				if not check(pii, pjj):
					continue
				if pii == bi and pjj == bj:
					(bii, bjj) = (bi + di, bj + dj)
					if not check(bii, bjj):
						continue
					if grid[bii][bjj] == 'T':
						return psh + 1
					st = (pii, pjj, bii, bjj)
					if st not in visited:
						visited.add(st)
						heapq.heappush(q, (psh + 1, pii, pjj, bii, bjj))
				else:
					st = (pii, pjj, bi, bj)
					if st not in visited:
						visited.add(st)
						heapq.heappush(q, (psh, pii, pjj, bi, bj))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		free = set(((i, j) for (i, row) in enumerate(grid) for (j, cell) in enumerate(row) if cell != '#'))
		target = next(((i, j) for (i, row) in enumerate(grid) for (j, cell) in enumerate(row) if cell == 'T'))
		(boxi, boxj) = next(((i, j) for (i, row) in enumerate(grid) for (j, cell) in enumerate(row) if cell == 'B'))
		(si, sj) = next(((i, j) for (i, row) in enumerate(grid) for (j, cell) in enumerate(row) if cell == 'S'))
		heap = [(0, si, sj, boxi, boxj)]

		def add(moves, *state, added=set()):
			if state not in added:
				heapq.heappush(heap, (moves, *state))
				added.add(state)
		while heap:
			(moves, si, sj, boxi, boxj) = heapq.heappop(heap)
			if (boxi, boxj) == target:
				return moves
			for (dx, dy) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
				(ni, nj) = (si + dx, dy + sj)
				if (ni, nj) == (boxi, boxj):
					if (boxi + dx, boxj + dy) in free:
						add(moves + 1, ni, nj, boxi + dx, boxj + dy)
				elif (ni, nj) in free:
					add(moves, ni, nj, boxi, boxj)
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		free = set()
		(m, n) = (len(grid), len(grid[0]))
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'T':
					(tx, ty) = (i, j)
					free.add((i, j))
				if grid[i][j] == 'S':
					(sx, sy) = (i, j)
					free.add((i, j))
				if grid[i][j] == 'B':
					(bx, by) = (i, j)
					free.add((i, j))
				if grid[i][j] == '.':
					free.add((i, j))
		pq = [(0, sx, sy, bx, by)]
		visited = set()
		direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		while pq:
			(moves, sx, sy, bx, by) = heapq.heappop(pq)
			if bx == tx and by == ty:
				return moves
			if (sx, sy, bx, by) in visited:
				continue
			visited.add((sx, sy, bx, by))
			for d in direction:
				(dx, dy) = d
				if sx + dx == bx and sy + dy == by and ((bx + dx, by + dy) in free):
					heapq.heappush(pq, (moves + 1, sx + dx, sy + dy, bx + dx, by + dy))
				if (sx + dx, sy + dy) in free and (sx + dx, sy + dy) != (bx, by) and ((sx + dx, sy + dy, bx, by) not in visited):
					heapq.heappush(pq, (moves, sx + dx, sy + dy, bx, by))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		self.m = len(grid)
		self.n = len(grid[0])
		(player, box) = ([0, 0], [0, 0])
		for i in range(self.m):
			for j in range(self.n):
				if grid[i][j] == 'B':
					box = [i, j]
				elif grid[i][j] == 'S':
					player = [i, j]
		(i, j) = box
		(x, y) = player
		q = collections.deque()
		q.append((i, j, x, y))
		visited = set()
		visited.add((i, j, x, y))
		step = 0
		dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		while q:
			size = len(q)
			for _ in range(size):
				(i, j, x, y) = q.popleft()
				if grid[i][j] == 'T':
					return step
				for (di, dj) in dirs:
					i2 = i + di
					j2 = j + dj
					if i2 < 0 or i2 >= self.m or j2 < 0 or (j2 >= self.n) or ((i2, j2, i, j) in visited) or (grid[i2][j2] == '#') or (not self.helper(grid, x, y, i, j, i - di, j - dj)):
						continue
					q.append((i2, j2, i, j))
					visited.add((i2, j2, i, j))
			step += 1
		return -1

	def helper(self, grid, x, y, bi, bj, i, j):
		visited = set()
		return self.has_path(grid, x, y, bi, bj, i, j, visited)

	def has_path(self, grid, x, y, bi, bj, i, j, visited):
		if x < 0 or x >= self.m or y < 0 or (y >= self.n) or (x == bi and y == bj) or (grid[x][y] == '#') or ((x, y) in visited):
			return False
		if x == i and y == j:
			return True
		visited.add((x, y))
		return self.has_path(grid, x - 1, y, bi, bj, i, j, visited) or self.has_path(grid, x + 1, y, bi, bj, i, j, visited) or self.has_path(grid, x, y + 1, bi, bj, i, j, visited) or self.has_path(grid, x, y - 1, bi, bj, i, j, visited)


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] == '.'):
				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


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'B':
					b = (i, j)
				if grid[i][j] == 'S':
					s = (i, j)
				if grid[i][j] == 'T':
					t = (i, j)
		queue = [(b[0], b[1], s[0], s[1], 0)]
		dic = {(b[0], b[1], s[0], s[1]): 0}
		res = float('inf')
		while queue:
			(bx, by, sx, sy, step) = queue.pop(0)
			if dic[bx, by, sx, sy] >= res:
				continue
			if (bx, by) == t:
				res = min(res, step)
				continue
			for i in range(4):
				nsx = sx + dx[i]
				nsy = sy + dy[i]
				if not 0 <= nsx < n or not 0 <= nsy < m or grid[nsx][nsy] == '#':
					continue
				if nsx == bx and nsy == by:
					nbx = bx + dx[i]
					nby = by + dy[i]
					if (nbx, nby, nsx, nsy) in dic and dic[nbx, nby, nsx, nsy] <= step + 1:
						continue
					dic[nbx, nby, nsx, nsy] = step + 1
					queue.append((nbx, nby, nsx, nsy, step + 1))
				else:
					if (bx, by, nsx, nsy) in dic and dic[bx, by, nsx, nsy] <= step:
						continue
					dic[bx, by, nsx, nsy] = step
					queue.append((bx, by, nsx, nsy, step))
		return res if res != float('inf') else -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		B = T = S = None
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'B':
					B = (i, j)
				if grid[i][j] == 'T':
					T = (i, j)
				if grid[i][j] == 'S':
					S = (i, j)
		heap = [(0, B[0], B[1], S[0], S[1])]
		heapq.heapify(heap)
		seen = set()
		while heap:
			(c, bi, bj, si, sj) = heapq.heappop(heap)
			if (bi, bj) == T:
				return c
			if (bi, bj, si, sj) in seen:
				continue
			seen.add((bi, bj, si, sj))
			for (nsi, nsj) in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
				if 0 <= nsi < n and 0 <= nsj < m and (grid[nsi][nsj] != '#'):
					if (nsi, nsj) != (bi, bj) and (bi, bj, nsi, nsj) not in seen:
						heapq.heappush(heap, (c, bi, bj, nsi, nsj))
					elif (bi, bj) == (nsi, nsj):
						(nbi, nbj) = (nsi - (si - nsi), nsj - (sj - nsj))
						if 0 <= nbi < n and 0 <= nbj < m and ((nbi, nbj, nsi, nsj) not in seen):
							heapq.heappush(heap, (c + 1, nbi, nbj, nsi, nsj))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		dire = [(1, 0), (0, 1), (-1, 0), (0, -1)]

		def can_get(cur_b, cur_p, tar):
			(seen, cur) = (set([cur_p]), set([cur_p]))
			while cur:
				tmp = []
				for loc in cur:
					for (x, y) in dire:
						if 0 <= loc[0] + x < len(grid) and 0 <= loc[1] + y < len(grid[0]) and ((loc[0] + x, loc[1] + y) != cur_b) and (grid[loc[0] + x][loc[1] + y] != '#') and ((loc[0] + x, loc[1] + y) not in seen):
							tmp += [(loc[0] + x, loc[1] + y)]
				cur = set(tmp)
				seen |= cur
				if tar in seen:
					return True
			return False
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'B':
					box = (i, j)
				if grid[i][j] == 'S':
					player = (i, j)
				if grid[i][j] == 'T':
					target = (i, j)
		(seen, cur, res) = (set([(box, player)]), set([(box, player)]), 0)
		while cur:
			tmp = []
			res += 1
			for (b, p) in cur:
				for (x, y) in dire:
					if 0 <= b[0] + x < len(grid) and 0 <= b[1] + y < len(grid[0]) and (grid[b[0] + x][b[1] + y] != '#') and can_get(b, p, (b[0] - x, b[1] - y)) and (((b[0] + x, b[1] + y), b) not in seen):
						tmp += [((b[0] + x, b[1] + y), b)]
			cur = set(tmp)
			seen |= cur
			for (x, y) in dire:
				if (target, (target[0] + x, target[1] + y)) in seen:
					return res
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'S':
					man = (i, j)
				elif grid[i][j] == 'B':
					box = (i, j)
				elif grid[i][j] == 'T':
					target = (i, j)

		def validPos(loc):
			(i, j) = loc
			return m > i >= 0 <= j < n and grid[i][j] != '#'

		def heuristic(box):
			return abs(target[0] - box[0]) + abs(target[1] - box[1])
		heap = [(heuristic(box), 0, man, box)]
		seen = set()
		dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		while heap:
			(_, steps, man, box) = heapq.heappop(heap)
			if box == target:
				return steps
			if (man, box) in seen:
				continue
			seen.add((man, box))
			for (r, c) in dirs:
				new_man = (man[0] + r, man[1] + c)
				if not validPos(new_man):
					continue
				if new_man == box:
					new_box = (box[0] + r, box[1] + c)
					if not validPos(new_box):
						continue
					heapq.heappush(heap, (heuristic(new_box) + steps + 1, steps + 1, new_man, new_box))
				else:
					heapq.heappush(heap, (heuristic(box) + steps, steps, new_man, box))
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'T':
					target = (i, j)
				elif grid[i][j] == 'B':
					start_box = (i, j)
				elif grid[i][j] == 'S':
					start_person = (i, j)

		def heuristic(box):
			return abs(target[0] - box[0]) + abs(target[1] - box[1])

		def out_bounds(location):
			(i, j) = location
			if i < 0 or i >= n:
				return True
			if j < 0 or j >= m:
				return True
			return grid[i][j] == '#'
		heap = [[heuristic(start_box), 0, start_person, start_box]]
		visited = set()
		while heap:
			(_, moves, person, box) = heapq.heappop(heap)
			if box == target:
				return moves
			if (person, box) in visited:
				continue
			visited.add((person, box))
			for (dx, dy) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
				new_person = (person[0] + dx, person[1] + dy)
				if out_bounds(new_person):
					continue
				if new_person == box:
					new_box = (box[0] + dx, box[1] + dy)
					if out_bounds(new_box):
						continue
					heapq.heappush(heap, [heuristic(new_box) + moves + 1, moves + 1, new_person, new_box])
				else:
					heapq.heappush(heap, [heuristic(box) + moves, moves, new_person, box])
		return -1


class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		(R, C) = (len(grid), len(grid[0]))
		b_pos = s_pos = t_pos = None
		for r in range(R):
			for c in range(C):
				if grid[r][c] == 'B':
					b_pos = (r, c)
				if grid[r][c] == 'S':
					s_pos = (r, c)
				if grid[r][c] == 'T':
					t_pos = (r, c)

		def is_empty(r, c):
			return 0 <= r < R and 0 <= c < C and (grid[r][c] != '#')
		visited = set()
		queue = [tuple(b_pos + s_pos)]
		steps = 0
		while queue:
			new_queue = []
			for (br, bc, sr, sc) in queue:
				new = (br, bc, sr, sc)
				if new in visited:
					continue
				visited.add(new)
				if (br, bc) == t_pos:
					return steps
				for (dr, dc) in dirs:
					(nsr, nsc) = (dr + sr, dc + sc)
					if (nsr, nsc) == (br, bc):
						(nbr, nbc) = (dr + br, dc + bc)
						box_move = True
					else:
						(nbr, nbc) = (br, bc)
						box_move = False
					if not is_empty(nsr, nsc) or not is_empty(nbr, nbc):
						continue
					new = (nbr, nbc, nsr, nsc)
					if box_move:
						new_queue.append(new)
					else:
						queue.append(new)
			queue = new_queue
			steps += 1
		return -1


import heapq

class Solution:

	def minPushBox(self, grid: List[List[str]]) -> int:
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'S':
					s = (i, j)
				if grid[i][j] == 'B':
					b = (i, j)
				if grid[i][j] == 'T':
					t = (i, j)

		def valid(i, j, s=None, b=None):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])):
				return False
			if grid[i][j] == '#':
				return False
			if s is not None:
				if (i, j) == s:
					return False
			if b is not None:
				if (i, j) == b:
					return False
			return True

		def next_state(s, b, step):
			for (di, dj) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
				if valid(s[0] + di, s[1] + dj):
					if b == (s[0] + di, s[1] + dj) and valid(b[0] + di, b[1] + dj):
						(nxt_s, nxt_b, nxt_step) = (b, (b[0] + di, b[1] + dj), step + 1)
					else:
						nxt_s = (s[0] + di, s[1] + dj)
						(nxt_b, nxt_step) = (b, step)
					yield (nxt_s, nxt_b, nxt_step)

		def edit_dis(s, b):
			return abs(s[0] - b[0]) + abs(s[1] - b[1])

		def search(s, b):
			q = [(0, edit_dis(s, b), s, b)]
			visited = {}
			visited[s, b] = 0
			while q:
				(step, _, s, b) = heapq.heappop(q)
				if b == t:
					return step
				for (nxt_s, nxt_b, nxt_step) in next_state(s, b, step):
					if (nxt_s, nxt_b) not in visited or visited[nxt_s, nxt_b] > nxt_step:
						q.append((nxt_step, edit_dis(nxt_s, nxt_b), nxt_s, nxt_b))
						visited[nxt_s, nxt_b] = nxt_step
			return -1
		return search(s, b)


class Solution:

	def init_positions(self):
		for i in range(self.m):
			for j in range(self.n):
				if self.grid[i][j] == 'S':
					pusher = (i, j)
				if self.grid[i][j] == 'B':
					box = (i, j)
				if self.grid[i][j] == 'T':
					target = (i, j)
		return (pusher, box, target)

	def bfs_from_pusher(self, pusher, box):
		visited = set()
		frontier = {pusher}
		while frontier:
			visited |= frontier
			new_frontier = set()
			for pos in frontier:
				for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					(new_x, new_y) = (pos[0] + dx, pos[1] + dy)
					if 0 <= new_x < self.m and 0 <= new_y < self.n and (self.grid[new_x][new_y] != '#') and ((new_x, new_y) != box) and ((new_x, new_y) not in visited):
						new_frontier.add((new_x, new_y))
			frontier = new_frontier
		return visited

	def reachable_neighbors_of(self, box, visited):
		for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			(new_x, new_y) = (box[0] + dx, box[1] + dy)
			if (new_x, new_y) in visited:
				(mir_x, mir_y) = (2 * box[0] - new_x, 2 * box[1] - new_y)
				if 0 <= mir_x < self.m and 0 <= mir_y < self.n and (self.grid[mir_x][mir_y] != '#'):
					yield (mir_x, mir_y)

	def minPushBox(self, grid: List[List[str]]) -> int:
		self.grid = grid
		self.m = len(grid)
		self.n = len(grid[0])
		(pusher, box, target) = self.init_positions()
		frontier = {(box, pusher)}
		visited = set()
		dist = 0
		while frontier:
			visited |= frontier
			for (box, _) in visited:
				if box == target:
					return dist
			new_frontier = set()
			for (cur_box, cur_pusher) in frontier:
				visited_pusher = self.bfs_from_pusher(cur_pusher, cur_box)
				for new_box in self.reachable_neighbors_of(cur_box, visited_pusher):
					if (new_box, cur_box) not in visited:
						new_frontier.add((new_box, cur_box))
			frontier = new_frontier
			dist += 1
		return -1