A 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 an m x n grid of characters grid where each element is a wall, floor, or box.

Your task is to move the box 'B' to the target position 'T' under the following rules:


	The character 'S' represents the player. The player can move up, down, left, right in grid if it is a floor (empty cell).
	The character '.' represents the floor which means a free cell to walk.
	The character '#' represents the wall which means an 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.

&nbsp;
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.


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 20
	grid contains only characters '.', '#', 'S', 'T', or 'B'.
	There is only one character 'S', 'B', and 'T' in the grid.


class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        m,n=len(grid),len(grid[0])
        q=deque()
        start,target,box=(0,0),(0,0),(0,0)
        for i in range(m):
            for j in range(n):
                if grid[i][j]=="B":
                    box=(i,j)
                elif grid[i][j]=="T":
                    target=(i,j)
                elif grid[i][j]=="S":
                    start=(i,j)
        q.append((box[0],box[1],0,start[0],start[1]))
        visited=set()
        directions=((1,0,-1,0),(0,1,0,-1),(-1,0,1,0),(0,-1,0,1))
        visited.add(box+box)
        def solve(i,j,bi,bj):
            nonlocal seen
            if (i,j)==(bi,bj):
                return True
            ans=False
            for d in directions:
                ni,nj=i+d[0],j+d[1]
                if 0<=ni<m and 0<=nj<n and (ni,nj) not in seen and grid[ni][nj]!="#":
                    seen.add((ni,nj))
                    ans=ans or solve(ni,nj,bi,bj)
                    if ans: return ans
            return ans
        while q:
            i,j,pushes,si,sj=q.popleft()
            if (i,j)==target:
                return pushes
            if pushes>m+n:
                return -1
            for d in directions:
                ni,nj,bi,bj=i+d[0],j+d[1],i+d[2],j+d[3]
                if 0<=ni<m and 0<=nj<n and (ni,nj,i,j) not in visited and grid[ni][nj]!="#" and 0<=bi<m and 0<=bj<n and grid[bi][bj]!="#":
                    seen=set()
                    seen.add((i,j))
                    grid[i][j]=="#"
                    res=solve(si,sj,bi,bj)
                    grid[i][j]="."
                    if not res:
                        continue
                    visited.add((ni,nj,i,j))
                    q.append((ni,nj,pushes+1,i,j))
        return -1
/**
  Finds Initial State (State consists of shopkeeper & box locations + # of boxMoves)
  Uses BFS/A* Algorithm to visit valid transition states
  Note: The min heuristic here is # of boxMoves + manHattanDistance between box & target locations
*/
class Solution {
    private int targetRow;
    private int targetCol;
    private char[][] grid;
    private static int[][] DIRS = {
            {1,0}, //Down
            {-1,0},//Up
            {0,1}, //Right
            {0,-1} //Left
    };

    /**
      State holds shopkeeper and box location, as well as how many times the box has been pushed
    */
    class State implements Comparable<State>{
        int personRow;
        int personCol;
        int boxRow;
        int boxCol;
        int boxPushes;

        public State(int personRow, int personCol, int boxRow, int boxCol, int boxPushes){
            this.personRow = personRow;
            this.personCol = personCol;
            this.boxRow = boxRow;
            this.boxCol = boxCol;
            this.boxPushes = boxPushes;
        }

        // Override equals - used along with hashcode when we have visited HashSet
        public boolean equals(Object o){
            State other = (State) o;
            return
            this.personRow == other.personRow &&
            this.personCol == other.personCol &&
            this.boxRow == other.boxRow &&
            this.boxCol == other.boxCol;
        }

        // Override the hashCode - Note: it's okay for this to have collisions
        // But it won't due to the problem constraint that there is a bound on NxM dimensions
        public int hashCode(){
            return personRow *10_000 + personCol * 1_000 + boxRow * 100 + boxCol;
        }

        // Override to string method - helpful in debugging state.
        public String toString(){
            return "ShopKeeper:{row:"+personRow+", col:"+personCol+"}" +
                   "Box:{row:"+boxRow+", col:"+boxCol+"}";
        }

        // Implement comparable interface such that we return the state that
        // has the possibility of lowest distance using box push count + Manhattan distance
        public int compareTo(State other){
            int minDistanceThis = this.boxPushes + distanceToTarget(this);
            int minDistanceOther = other.boxPushes + distanceToTarget(other);
            return Integer.compare(minDistanceThis, minDistanceOther);
        }

    }

    // Calculates Manhattan distance
    private int distanceToTarget(State state){
        int yDiff = Math.abs(state.boxCol - targetCol);
        int xDiff = Math.abs(state.boxRow - targetRow);
        return yDiff + xDiff;
    }

    /**
       Given a state, compare box location to target location to determine if it is
       a solution state.
    */
    private boolean isSolutionState(State state){
        return state.boxRow == targetRow && state.boxCol == targetCol;
    }

    /**
        Given a state, finds all valid transition states.
        This is accomplished by moving the ShopKeeper in all 4 directions and validate
        - Next ShopKeeper location is in bounds and is not a wall

        We have additional logic for when the next shopkeeper location is the box location:
        - Get next box location, by pushing the same direction, again validate that
          the next box location is in bounds, and is not a wall.

        If it's a valid transition, create the new state with the new shop keeper location
        and if the box moved, the new box location (also increment the number of box moves).

    **/
    private List<State> getNeighbors(State state){

        int personRow = state.personRow;
        int personCol = state.personCol;
        int boxRow = state.boxRow;
        int boxCol = state.boxCol;

        List<State> states = new ArrayList<>();
        for(int[] dir : DIRS){
            int rowMove = dir[0];
            int colMove = dir[1];
            int personRowNew = personRow + rowMove;
            int personColNew = personCol + colMove;
            // Shopkeeper cannot move into wall or go out of bounds skip to next direction
            if(!inBounds(personRowNew, personColNew) ||
               isWall(personRowNew, personColNew)){
                continue;
            }
            // Whether or not person will collide with box
            boolean willPushBox = personRowNew == boxRow && personColNew == boxCol;

            if(willPushBox){
                int boxRowNew = boxRow + rowMove;
                int boxColNew = boxCol + colMove;
                // Validate box can be pushed - if so push box and add to neighbor states
                if(inBounds(boxRowNew, boxColNew) &&
                   !isWall(boxRowNew, boxColNew)){
                   states.add(new State(personRowNew, personColNew, boxRowNew, boxColNew, state.boxPushes + 1));
                }
            } else {
                //Shop keeper moved, but not box
                states.add(new State(personRowNew, personColNew, boxRow, boxCol, state.boxPushes));
            }
        }
        return states;

    }

    // Given row/col, return whether it is wall
    private boolean isWall(int row, int col){
        char cell = grid[row][col];
        return cell == '#';
    }

    // Given row/col return whether is inBounds
    private boolean inBounds(int row, int col){
        int rows = grid.length;
        int cols = grid[0].length;
        if(row < 0 || col < 0 || row > rows-1 || col > cols-1){
            return false;
        }
        return true;
    }

    /**
      Returns initial state. Also finds and stores the target location.
    */
    private State getInitialState(){

        int shopKeeperRow=0;
        int shopKeeperCol=0;

        int boxRow = 0;
        int boxCol = 0;

        for(int r=0; r<grid.length; r++){
            char[] row = grid[r];
            for(int c=0; c<row.length; c++){
                char cell = grid[r][c];
                if(cell == 'T'){
                    this.targetRow = r;
                    this.targetCol = c;
                }
                else if(cell == 'B'){
                    boxRow = r;
                    boxCol = c;
                } else if(cell == 'S'){
                    shopKeeperRow = r;
                    shopKeeperCol = c;
                }
            }
        }

        return new State(shopKeeperRow, shopKeeperCol, boxRow, boxCol, 0);
    }

    public int minPushBox(char[][] grid) {
        this.grid = grid;

        State initialState = getInitialState();
        Queue<State> queue = new PriorityQueue<>();
        Set<State> visited = new HashSet<>();
        queue.offer(initialState);

        // Explore every state using BSF and keep track of the best solution
        while(!queue.isEmpty()){
            State state = queue.poll();
            if(visited.contains(state)){
                continue;
            }
            visited.add(state);
            /*
              Note: the reason we can return the first solution state we find, is because we are
              using priority queue with minDistance heuristic which means the first solution we find
              is guaranteed to be the optimal solution - (A* Algorithm)
            */
            if(isSolutionState(state)){
                return state.boxPushes;
            }
            for(State neighbor : getNeighbors(state)){
                if(!visited.contains(neighbor)){
                    queue.offer(neighbor);
                }
            };
        }
        // No solution - return -1
        return -1;
    }

}
class Solution {
public:
    
    pair<int,int> t; //target
    pair<int,int> s; //source
    pair<int,int> b; //box
    
    // struct to store each member in priority queue
    struct node {
        int heuristic; // to find the dist between target and box
        int dist; // to keep track of how much the box moved
        pair<int,int> src; // to store the source
        pair<int,int> dest; // to store the box location
    };
    
    struct comp {
        bool operator()(node const& a, node const& b){
            return a.heuristic + a.dist > b.heuristic + b.dist;
        }
    };
 
    int direction[4][2]= {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
    
    int minPushBox(vector<vector<char>>& grid) {
        
        int m=grid.size();
        int n=grid[0].size();
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='T')
                    t={i,j};
                
                else if(grid[i][j]=='B')
                    b={i,j};
                
                else if(grid[i][j]=='S')
                    s={i,j};
            }
        }
        
        priority_queue<node,vector<node>,comp> pq;
        set<string> visited;
        
        node initialState = node{manhattanDist(b.first,b.second),0,s,b};
        string initialStr = hash(initialState);
        
        pq.push(initialState);
                
        while(!pq.empty()){
            auto cur = pq.top();
            pq.pop();
            
            // we have reached the target return
            if(cur.dest == t) 
                return cur.dist;
            
            // hash the cur string and 
            string cur_vis = hash(cur);
            if(visited.count(cur_vis)) continue;
            
            // mark it as visited
            visited.insert(cur_vis);
            
            // in all the four directions
            for(auto& dir:direction){
                int sx = cur.src.first + dir[0];
                int sy = cur.src.second + dir[1];
                
                // if the new source is valid index
                if(valid(sx,sy,grid)){
                    
                    //if the source is equal to the where the box is
                    if(sx == cur.dest.first && sy == cur.dest.second){
                        int bx=cur.dest.first + dir[0];
                        int by=cur.dest.second + dir[1];
                        
                        // if the box is at right position
                        if(valid(bx,by,grid)){
                            
                            // increment the dist by 1 and update the source and box location
                            node updated = node{manhattanDist(bx,by),cur.dist+1,{sx,sy},{bx,by}};
                            pq.push(updated);
                        }
                    }else{
                        // update the new location of source 
                        node updated = node{cur.heuristic,cur.dist,{sx,sy},cur.dest};
                        pq.push(updated);
                    }
                }
            }
        }
        
        // we cannot perform the operation
        return -1;
        
    }
    
    string hash(node t){
        stringstream ss;
        ss<<t.src.first<<" "<<t.src.second<<" "<<t.dest.first<<" "<<t.dest.second;
        return ss.str();
    }
    
    int manhattanDist(int i, int j){
        return abs(t.first-i) + abs(t.second-j);
    }
    
    bool valid(int i, int j, vector<vector<char>>& g){
        
        if(i<0 || j<0 || i>=g.size() || j>=g[0].size() || g[i][j]=='#') return false;
        
        return true;
    }
};
/**
 * @param {character[][]} grid
 * @return {number}
 */
var minPushBox = function(grid) {
    // common info & utils
    const m = grid.length
    const n = grid[0].length
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    const add = (a, b) => [a[0] + b[0], a[1] + b[1]]
    const equals = (a, b) => a[0] === b[0] && a[1] === b[1]
    const validate = ([x, y]) => x >= 0 && y >= 0 && x < m && y < n
    const getKey = ([x, y]) => x * n + y

    // find all player, ball, target, and free cells
    const init = () => {
        let player
        let ball
        let target
        const freeSet = new Set()
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === '.') {
                    freeSet.add(getKey([i, j]))
                } else if (grid[i][j] === 'S') {
                    freeSet.add(getKey([i, j]))
                    player = [i, j]
                } else if (grid[i][j] === 'B') {
                    freeSet.add(getKey([i, j]))
                    ball = [i, j]
                } else if (grid[i][j] === 'T') {
                    freeSet.add(getKey([i, j]))
                    target = [i, j]
                }
            }
        }
        return { player, ball, target, freeSet }
    }
    const { player, ball, target, freeSet } = init()
    const targetKey = getKey(target)

    // detect whether two cells are connected
    const connCache = new Map() // [x,y,x2,y2,x3,y3] => boolean
    const getConnKey = (a, b, ball) => {
        if (
            a[0] > b[0] ||
            a[0] === b[0] && a[1] > b[1]
        ) {
            [a, b] = [b, a]
        }
        return [a[0], a[1], b[0], b[1], ball[0], ball[1]].join(',')
    }
    const isConnected = (a, b, ball) => {
        if (a[0] === b[0] && a[1] === b[1]) {
            return true
        }
        const connKey = getConnKey(a, b, ball)
        if (connCache.has(connKey)) {
            return connCache.get(connKey)
        }
        const bKey = getKey(b)
        const ballKey = getKey(ball)
        const visited = new Array(m * n).fill(false)
        visited[getKey(a)] = true
        const queue = [a]
        while (queue.length) {
            const cell = queue.shift()
            for (let i = 0; i < dirs.length; i++) {
                const next = add(cell, dirs[i])
                if (validate(next)) {
                    const nextKey = getKey(next)
                    if (nextKey === bKey) {
                        connCache.set(connKey, true)
                        return true
                    }
                    if (
                        freeSet.has(nextKey) &&
                        nextKey !== ballKey &&
                        !visited[nextKey]
                    ) {
                        visited[nextKey] = true
                        queue.push(next)
                    }
                }
            }
        }
        connCache.set(connKey, false)
        return false
    }

    // solve the game
    const getStateKey = ([x, y], [xx, yy]) => [x, y, xx, yy].join(',') // ball, player
    const stateCache = new Set() // Set<stateKey>
    let queue = [[ball, player]]
    let count = 1
    while (queue.length) {
        const nextQueue = []
        for (let i = 0; i < queue.length; i++) {
            const [ball, player] = queue[i]
            for (let j = 0; j < dirs.length; j++) {
                const dir = dirs[j]
                const reverseDir = [dir[0] ? -dir[0] : 0, dir[1] ? -dir[1] : 0]
                const nextBall = add(ball, dir)
                const nextPlayer = add(ball, reverseDir)
                const nextBallKey = getKey(nextBall)
                const nextPlayerKey = getKey(nextPlayer)
                if (
                    validate(nextBall) &&
                    validate(nextPlayer) &&
                    freeSet.has(nextBallKey) &&
                    freeSet.has(nextPlayerKey)
                ) {
                    const nextStateKey = getStateKey(nextBall, nextPlayer)
                    if (isConnected(player, nextPlayer, ball)) {
                        if (!stateCache.has(nextStateKey)) {
                            stateCache.add(nextStateKey)
                            if (nextBallKey === targetKey) {
                                return count
                            }
                            nextQueue.push([nextBall, nextPlayer])
                        }
                    }
                }
            }
        }
        queue = nextQueue
        count++
    }
    return -1
};
Minimum Moves to Move a Box to Their Target Location