Algorithm (0-1 BFS)

1. Construct a weighted graph $G = (V, E, W)$ where elements in $V$ are of the form $(r_{\text{box}}, c_{\text{box}}, r_{\text{player}}, c_{\text{player}})$. Here $r, c$ refer to the coordinates of the grid.
2. Note that there is an edge between $(r_{\text{box}}, c_{\text{box}}, r_{\text{player}}, c_{\text{player}})$ and $(r_{\text{box}}^{\’}, c_{\text{box}}^{\’}, r_{\text{player}}^{\’}, c_{\text{player}}^{\’})$ if and only if the player can move from the former to the latter in one move following to rules given in the problem.
3. Note note that any edge $(r_{\text{box}}, c_{\text{box}}, r_{\text{player}}, c_{\text{player}})$ $\rightarrow$ $(r_{\text{box}}^{\’}, c_{\text{box}}^{\’}, r_{\text{player}}^{\’}, c_{\text{player}}^{\’})$ has weight 1 if $(r_{\text{box}}, c_{\text{box}}) \neq (r_{\text{box}}^{\’}, c_{\text{box}}^{\’}) $ and 0 otherwise.
4. Then the problem is reduced to finding the shortest path from the starting point to the end point, both of which are deterministic.
5. Because the weights are 0, 1, we could use double ended queue to simulate Dijkstra in order to speed things up. This is also called 0-1 BFS.
6. The total time complexity is around $O(N^4)$ where $N = \max\{R, C\}$.

Code

class Solution {
 public:
  int minPushBox(vector<vector<char>>& grid) {
    const int R = size(grid);
    const int C = size(grid[0]);
    const int dr[4] = {1, -1, 0, 0};
    const int dc[4] = {0, 0, 1, -1};

    struct node_t {
      const int box_r;
      const int box_c;
      const int person_r;
      const int person_c;
    };

    struct state_t {
      mutable deque<node_t> Q;
      mutable optional<int> D[20][20][20][20];
    };

    auto valid = [&](int r, int c) {
      return r >= 0 and r < R and c >= 0 and c < C and grid[r][c] != '#';
    };

    const auto init_player = [&]() -> array<int, 2> {
      for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
          if (grid[r][c] == 'S')
            return {r, c};
      throw std::domain_error("not player");
    }();

    const auto init_box = [&]() -> array<int, 2> {
      for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
          if (grid[r][c] == 'B')
            return {r, c};
      throw std::domain_error("not init");
    }();

    const auto target = [&]() -> array<int, 2> {
      for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
          if (grid[r][c] == 'T')
            return {r, c};
      throw std::domain_error("no target");
    }();

    auto walk = [&](const node_t & node, int i) -> optional<node_t> {
      const auto [br, bc, pr, pc] = node;
      const auto [next_pr, next_pc] = tuple(pr + dr[i], pc + dc[i]);
      const auto [next_br, next_bc] = [&] {
        if (next_pr == br and next_pc == bc)
          return tuple(br + dr[i], bc + dc[i]);
        else
          return tuple(br, bc);
      }();
      if (valid(next_br, next_bc) and valid(next_pr, next_pc))
        return node_t{next_br, next_bc, next_pr, next_pc};
      else
        return {};
    };

    const int solution = [&] {
      const auto [Q, D] = state_t{deque<node_t>{node_t{init_box[0], init_box[1],
                                                  init_player[0], init_player[1]}},
                             {}};
      for (D[init_box[0]][init_box[1]][init_player[0]][init_player[1]];
           not empty(Q);) {
        const auto [br, bc, pr, pc] = Q.front();

        Q.pop_front();
        if (br == target[0] and bc == target[1])
          return *D[br][bc][pr][pc];
        else {
          for (int i = 0; i < 4; ++i) {
            const auto next = walk({br, bc, pr, pc}, i);
            if (next.has_value()) {
              const auto [nbr, nbc, npr, npc] = next.value();
              if (nbr == br and nbc == bc) {
                if (not D[nbr][nbc][npr][npc]) {
                  D[nbr][nbc][npr][npc] = *D[br][bc][pr][pc];
                  Q.emplace_front(node_t{nbr, nbc, npr, npc});
                }
              }
              else if (nbr != br or nbc != bc) {
                if (not D[nbr][nbc][npr][npc]) {
                  D[nbr][nbc][npr][npc] = *D[br][bc][pr][pc] + 1;
                  Q.emplace_back(node_t{nbr, nbc, npr, npc});
                }
              }
            }
          }
        }
      }
      return -1;
    }();
    return solution;
  }
};