Minimum Moves to Move a Box to Their Target Location LeetCode solution in C++

1
struct node {
2
  int x, y;
3
  node(int xx, int yy) {
4
    x = xx;
5
    y = yy;
6
  }
7
};
8

9
struct node2 {
10
  int x, y, dir;
11
  node2(int xx, int yy, int dd) {
12
    x = xx;
13
    y = yy;
14
    dir = dd;
15
  }
16
};
17

18
class Solution {
19
  vector<vector<int>> dfn;
20
  vector<vector<vector<int>>> color;
21
  vector<vector<vector<bool>>> cover;
22
  vector<vector<int>> mi;
23
  vector<vector<char>> grid;
24
  int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
25
  int id;
26
  int sid;
27
  vector<vector<bool>> ins;
28
  stack<node2> st;
29
  int n, m;
30

31
  void dfs(int x, int y, int last_dir) {
32
    dfn[x][y] = mi[x][y] = ++id;
33
    int i;
34

35
    for (i = 0; i < 4; i++) {
36
      if ((last_dir ^ 1) == i) {
37
        continue;
38
      }
39
      int nx, ny;
40
      nx = x + dir[i][0];
41
      ny = y + dir[i][1];
42

43
      if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#') {
44
        if (cover[x][y][i] == 0 && cover[nx][ny][i ^ 1] == 0) {
45
          st.push(node2(x, y, i));
46
          cover[x][y][i] = cover[nx][ny][i ^ 1] = 1;
47
        }
48
        if (dfn[nx][ny] == 0) {
49
          dfs(nx, ny, i);
50
          if (dfn[x][y] <= mi[nx][ny]) {
51
            node2 now(0, 0, 0);
52
            do {
53
              now = st.top();
54
              st.pop();
55
              color[now.x][now.y][now.dir] = sid;
56
              color[now.x + dir[now.dir][0]][now.y + dir[now.dir][1]][now.dir ^ 1] = sid;
57
            } while (now.x != x || now.y != y || now.dir != i);
58
            sid++;
59
          }
60
          mi[x][y] = min(mi[x][y], mi[nx][ny]);
61
        } else // if(ins[nx][ny]==1)
62
        {
63
          mi[x][y] = min(mi[x][y], dfn[nx][ny]);
64
        }
65
      }
66
    }
67
    return;
68
  }
69

70
 public:
71
  int minPushBox(vector<vector<char>> &grid) {
72
    this->grid = grid;
73
    n = grid.size();
74
    m = grid[0].size();
75
    int i, j, k;
76
    dfn = vector<vector<int>>(n, vector<int>(m, 0));
77
    color = vector<vector<vector<int>>>(n, vector<vector<int>>(m, vector<int>(4, 0)));
78
    cover = vector<vector<vector<bool>>>(n, vector<vector<bool>>(m, vector<bool>(4, 0)));
79
    mi = vector<vector<int>>(n, vector<int>(m, INT_MAX));
80
    ins = vector<vector<bool>>(n, vector<bool>(m, 0));
81
    id = 0;
82
    sid = 1;
83
    for (i = 0; i < n; i++) {
84
      for (j = 0; j < m; j++) {
85
        if (grid[i][j] != '#' && dfn[i][j] == 0) {
86
          dfs(i, j, -1);
87
        }
88
      }
89
    }
90

91
    int sx, sy, ex, ey, bx, by;
92
    for (i = 0; i < n; i++) {
93
      for (j = 0; j < m; j++) {
94
        if (grid[i][j] == 'S') {
95
          sx = i;
96
          sy = j;
97
        }
98

99
        if (grid[i][j] == 'T') {
100
          ex = i;
101
          ey = j;
102
        }
103

104
        if (grid[i][j] == 'B') {
105
          bx = i;
106
          by = j;
107
        }
108
      }
109
    }
110

111
    ins = vector<vector<bool>>(n, vector<bool>(m, 0));
112
    queue<node> q;
113
    queue<node2> q2;
114
    q.push(node(sx, sy));
115
    ins[sx][sy] = 1;
116
    int dp[n][m][4];
117
    memset(dp, -1, sizeof(dp));
118

119
    while (!q.empty()) {
120
      node now = q.front();
121
      q.pop();
122
      for (i = 0; i < 4; i++) {
123
        int nx, ny;
124
        nx = now.x + dir[i][0];
125
        ny = now.y + dir[i][1];
126
        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
127
          if (nx == bx && ny == by) {
128
            dp[bx][by][i ^ 1] = 0;
129
            q2.push(node2(bx, by, i ^ 1));
130
          } else if (grid[nx][ny] != '#' && ins[nx][ny] == 0) {
131
            ins[nx][ny] = 1;
132
            q.push(node(nx, ny));
133
          }
134
        }
135
      }
136
    }
137

138
    while (!q2.empty()) {
139
      node2 now = q2.front();
140
      q2.pop();
141

142
      if (now.x == ex && now.y == ey) {
143
        return dp[now.x][now.y][now.dir];
144
      }
145

146
      int nx, ny;
147

148
      for (i = 0; i < 4; i++) {
149
        if (i == now.dir) {
150
          continue;
151
        }
152

153
        nx = now.x + dir[i][0];
154
        ny = now.y + dir[i][1];
155
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#' &&
156
            dp[now.x][now.y][i] == -1 && color[now.x][now.y][now.dir] == color[now.x][now.y][i]) {
157
          dp[now.x][now.y][i] = dp[now.x][now.y][now.dir];
158
          q2.push(node2(now.x, now.y, i));
159
        }
160
      }
161

162
      int d = (now.dir ^ 1);
163
      nx = now.x + dir[d][0];
164
      ny = now.y + dir[d][1];
165
      if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#' &&
166
          dp[nx][ny][now.dir] == -1) {
167
        dp[nx][ny][now.dir] = dp[now.x][now.y][now.dir] + 1;
168
        q2.push(node2(nx, ny, now.dir));
169
      }
170
    }
171

172
    return -1;
173
  }
174
};