✅✅✅Easiest Solution || Beats 76.69% || BFS Solution for LeetCode#1263✅✅✅✅
IntuitionThe problem requires pushing a box ('B') to a target ('T') while controlling a player ('S') in a grid with obstacles ('#'). The challenge is that the p
![Screenshot 2025-02-19 at 10.36.23 PM.png](https://assets.leetcode.com/users/images/cec2da21-1e26-4051-bd9c-8ca0c2f01994_1739985442.2946978.png)

# Intuition
The problem requires pushing a box ('B') to a target ('T') while controlling a player ('S') in a grid with obstacles ('#'). The challenge is that the player must be in the correct position to push the box, and movement is constrained by walls.

Since we want to minimize the number of pushes, we need a shortest-path approach that prioritizes states with fewer pushes. This suggests using Dijkstra’s algorithm (priority queue / min-heap) to always expand the most promising state first.
# Approach

State Representation

Each state is represented as (boxX, boxY, playerX, playerY, pushes).
We track the box position, the player position, and the number of pushes made so far.
The goal is to move the box to the target (T) with the fewest pushes.
Priority Queue (Min-Heap)

We use a min-heap (priority_queue) to always process states with fewer pushes first.
This ensures we find the shortest push sequence optimally.
Valid Moves

The box moves only when pushed by the player.
The player must reach the correct pushing position before each move.
The box cannot move into walls ('#') or go out of bounds.
Algorithm (Dijkstra-like BFS with Priority Queue)

Initialize the priority queue with the starting state (boxX, boxY, playerX, playerY, 0 pushes).
Use BFS with a priority queue:
Extract the state with the least pushes.
Try all four possible box moves (right, left, down, up):
Compute the new box position.
Compute the required player position to push the box.
Check if the player can reach the required position (using BFS).
If valid, add the new state to the priority queue.
Return the minimum number of pushes when the box reaches the target.
If the box cannot reach the target, return -1.


# Complexity
- Time complexity: O( m^2 * n^2 )
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O( m^2 * n^2 )
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    bool isValid(const vector<vector<char>>& grid, int x, int y) {
        return x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size() &&
               grid[x][y] != '#';
    }

    bool canReach(const vector<vector<char>>& grid, int startX, int startY,
                  int targetX, int targetY, int boxX, int boxY) {
        queue<pair<int, int>> q;
        q.push({startX, startY});
        vector<vector<bool>> visited(grid.size(),
                                     vector<bool>(grid[0].size(), false));
        visited[startX][startY] = true;

        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            if (x == targetX && y == targetY)
                return true;

            for (auto [dx, dy] : directions) {
                int newX = x + dx, newY = y + dy;

                if (isValid(grid, newX, newY) && !visited[newX][newY] &&
                    !(newX == boxX && newY == boxY)) {
                    visited[newX][newY] = true;
                    q.push({newX, newY});
                }
            }
        }
        return false;
    }

    int minPushBox(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> box, player, target;

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'B')
                    box = {i, j};
                if (grid[i][j] == 'S')
                    player = {i, j};
                if (grid[i][j] == 'T')
                    target = {i, j};
            }

        queue<tuple<int, int, int, int, int>> q;
        q.push({box[0], box[1], player[0], player[1], 0});

        vector<vector<vector<vector<bool>>>> visited(
            m, vector<vector<vector<bool>>>(
                   n, vector<vector<bool>>(m, vector<bool>(n, false))));

        visited[box[0]][box[1]][player[0]][player[1]] = true;

        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        while (!q.empty()) {
            auto [boxX, boxY, playerX, playerY, pushes] = q.front();
            q.pop();

            if (boxX == target[0] && boxY == target[1])
                return pushes;

            for (auto [dx, dy] : directions) {
                int newBoxX = boxX + dx, newBoxY = boxY + dy;
                int pushPosX = boxX - dx, pushPosY = boxY - dy;

                if (!isValid(grid, newBoxX, newBoxY) ||
                    !isValid(grid, pushPosX, pushPosY))
                    continue;

                if (visited[newBoxX][newBoxY][boxX][boxY])
                    continue;

                if (canReach(grid, playerX, playerY, pushPosX, pushPosY, boxX, boxY)) {
                    visited[newBoxX][newBoxY][boxX][boxY] = true;
                    q.push({newBoxX, newBoxY, boxX, boxY, pushes + 1});
                }
            }
        }
        return -1;
    }
};


```
['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'Matrix', 'C++']