1263. Minimum Moves to Move a Box to Their Target Location

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.

class Solution {
    array<bool,4> bfs(vector<vector<char>>& grid, int y, int x, int by, int bx) {
        int n = grid.size(), m = grid[0].size();
        bool vis[20][20];
        memset(vis,false,sizeof(vis));
        int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
        queue<pair<int,int>> q;
        q.push({y,x});
        vis[y][x] = true;
        while(!q.empty()) {
            y = q.front().first, x = q.front().second;
            q.pop();
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                if(0 <= ny and ny < n and 0 <= nx and nx < m and !vis[ny][nx] and grid[ny][nx] != '#') {
                    vis[ny][nx] = true;
                    q.push({ny,nx});
                }
            }
        }
        return {
            by - 1 >= 0 ? vis[by-1][bx] : false,
            bx + 1 < m ? vis[by][bx+1] : false,
            by + 1 < n ? vis[by+1][bx] : false,
            bx - 1 >= 0 ? vis[by][bx-1] : false};
    }
public:
    int minPushBox(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        bool vis[20][20][20][20];
        memset(vis,false,sizeof(vis));
        int bx, by, sx, sy;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 'B') {
                    by = i, bx = j;
                    grid[i][j] = '.';
                } else if(grid[i][j] == 'S') {
                    sy = i, sx = j;
                    grid[i][j] = '.';
                }
            }
        }
        
        int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
        queue<array<int,4>> q;
        q.push({by,bx,sy,sx});
        vis[by][bx][sy][sx] = true;
        
        int res = 1;
        while(!q.empty()) {
            int sz = q.size();
            while(sz--) {
                by = q.front()[0], bx = q.front()[1], sy = q.front()[2], sx = q.front()[3];
                q.pop();
                grid[by][bx] = '#';
                auto mv = bfs(grid, sy, sx, by, bx);
                grid[by][bx] = '.';
                for(int i = 0; i < 4; i++) {
                    if(!mv[(i+2)%4]) continue;
                    int ny = by + dy[i], nx = bx + dx[i];
                    if(0 <= ny and ny < n and 0 <= nx and nx < m and grid[ny][nx] != '#' and !vis[ny][nx][by][bx]) {
                        q.push({ny,nx,by,bx});
                        vis[ny][nx][by][bx] = true;
                        if(grid[ny][nx] == 'T') return res;
                    }
                }
            }
            res++;
        }
        return -1;
    }
};