1
class Solution {
2
 public:
3
  vector<vector<char>> rotateTheBox(vector<vector<char>> &box) {
4
    int m = box.size();
5
    int n = box[0].size();
6

7
    vector<vector<char>> ans(n, vector<char>(m, '.'));
8

9
    for (int i = 0; i < m; ++i) {
10
      int k = n; // Stores last obstacle or occupied position
11
      for (int j = n - 1; j >= 0; --j) {
12
        if (box[i][j] == '#') {
13
          ans[--k][i] = '#';
14
        } else if (box[i][j] == '*') {
15
          k = j;
16
          ans[j][i] = '*';
17
        }
18
      }
19
    }
20
    for (int i = 0; i < n; ++i) {
21
      reverse(ans[i].begin(), ans[i].end());
22
    }
23
    return ans;
24
  }
25
};