You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the box is one of the following:

• A stone '#'
• A stationary obstacle '*'
• Empty '.'

The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.

It is guaranteed that each stone in box rests on an obstacle, another stone, or the bottom of the box.

Return an n x m matrix representing the box after the rotation described above.

Example 1:

Input: box = [["#",".","#"]]
Output: [["."],
         ["#"],
         ["#"]] 

Example 2:

Input: box = [["#",".","*","."],
              ["#","#","*","."]]
Output: [["#","."],
         ["#","#"],
         ["*","*"],
         [".","."]]

Example 3:

Input: box = [["#","#","*",".","*","."],
              ["#","#","#","*",".","."],
              ["#","#","#",".","#","."]]
Output: [[".","#","#"],
         [".","#","#"],
         ["#","#","*"],
         ["#","*","."],
         ["#",".","*"],
         ["#",".","."]]

Constraints:

• m == box.length
• n == box[i].length
• 1 <= m, n <= 500
• box[i][j] is either '#', '*', or '.'.

Here is one for you   m x n   Character matrix of   box  ， It represents a side view of a box. Each grid of the box may be:

• '#'   It means stone
• '*'   Indicates a fixed obstacle
• '.'   Indicates an empty position

The box is rotated 90 degrees clockwise  ， Because of gravity, the position of some stones will change. Each stone will fall vertically until it meets an obstacle, another stone or the bottom of the box. Gravity will not   Affect the position of the obstacle, and the rotation of the box will not produce inertia  ， That is to say, the horizontal position of the stone will not change.

The title is guaranteed at the beginning   box   The stones in the box are either on one obstacle, on another, or at the bottom of the box. Please return one   The matrix of n x m represents the result in the box after the above rotation.

Solution 1 violence simulation

When we rotate the box clockwise, each row becomes a new row. Because the stone only falls vertically under the action of gravity, each row does not affect each other. We simulate the results of each row in turn, that is, we get the results of each new column. Note that since gravity is down, you should traverse each row from right to left.

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size(), n = box[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                if (box[i][j] == '#'{/ / if there is a bottom or an obstacle or a stone under the stone, the position remains unchanged
                    if (j == n - 1 || box[i][j + 1] == '*' || box[i][j + 1] == '#') continue;
                    box[i][j] = '.'; //Otherwise, it becomes empty
                    for (int k = j; k < n; ++k) {
                        if (k == n - 1 || box[i][k + 1] == '*' || box[i][k + 1] == '#') {
                            box[i][k] = '#'; 
                            break;
                        }
                    }
                }
            }
        }
        vector<vector<char>> ans(n, vector<char>(m)); //The matrix rotates 90 degrees clockwise
        for (int i = m - 1; i >= 0; --i) for (int j = 0; j < n; ++j) ans[j][m - i - 1] = box[i][j];
        return ans;
    }
};

The operation efficiency is as follows:

Execution time: 364 ms, At all C++ 18 in the submission.55% Users of
 Memory consumption: 51.3 MB, At all C++ 48 in the submission.77% Users of

Solution 2 queue maintenance vacancy

If from right to left, we search for the right position for each stone that needs to fall vertically. We can't help repeating the operation. We can put the stones in the right position in batches.

Specifically, when we traverse from right to left, we record each vacancy; When encountering obstacles, clear the currently recorded vacancies, because the vacancies on the right side of the obstacles are useless; When encountering a stone (and the vacancy queue is not empty), take out the first vacancy in our current record and put the stone in. At this time, the position of the stone becomes empty and needs to be added to the queue. It is not difficult to find that this is a first in first out operation sequence, so queues are needed.

This way, you only need to process the original line O ( n ) O(n) O(n) complexity, only O ( m n ) O(mn) Time complexity of O(mn). The space needed by the queue is O ( n ) O(n) O(n) .

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size(), n = box[0].size();
        for (int i = 0; i < m; ++i) {
            deque<int> q;
            for (int j = n - 1; j >= 0; --j) { 
                if (box[i][j] == '.') q.push_back(j); //Put the empty position in the queue
                else if (box[i][j] == '*') q.clear(); //Clear queue
                else if (box[i][j] == '#' && !q.empty()) { 
                    swap(box[i][j], box[i][q.front()]); 
                    q.pop_front(); 
                    q.push_back(j); //At this time, the position of the stone has become vacant
                }
            }
        }
        vector<vector<char>> ans(n, vector<char>(m));
        for (int i = m - 1; i >= 0; --i) for (int j = 0; j < n; ++j) ans[j][m - i - 1] = box[i][j];
        return ans;
    }
};

The operation efficiency is significantly improved

Execution time: 280 ms, At all C++ 46 in the submission.67% Users of
 Memory consumption: 55.5 MB, At all C++ 16 in the submission.10% Users of

Solution 3 double pointer

Think about it, we can even do without queues! Since each row or new column is independent, we deal with each row separately, moving the stone to the right, to the bottom, to the obstacle, or to other stones - isn't it very similar to moving zero to move some element to the end of the array? Therefore, through careful consideration, we can get a double pointer solution.

This method can also be considered from solution 2. In solution 2, after traversing a position j, if the queue is not empty (there is no obstacle, position j is a stone or a vacancy), then the tail of the queue must be position j, and the position must be a vacancy, or it was originally a stone but fell into a vacancy; The positions in the queue must be continuous. Therefore, we only need to maintain the corresponding position of the head of the queue, and the whole queue exists implicitly.

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size(), n = box[0].size();
        for (int i = 0; i < m; ++i) { 
            int pos = n - 1; //The position of the team leader
            for (int j = n - 1; j >= 0; --j) { 
                if (box[i][j] == '*') pos = j - 1; //When encountering obstacles, clear the queue and change the position of the leader
                else if (box[i][j] == '#' ) { 
                    swap(box[i][j], box[i][pos]);
                    --pos;
                }
            }
        }
        vector<vector<char>> ans(n, vector<char>(m));
        for (int i = m - 1; i >= 0; --i) for (int j = 0; j < n; ++j) ans[j][m - i - 1] = box[i][j];
        return ans;
    }
};

The operation efficiency is as follows:

Execution time: 256 ms, At all C++ 84 in the submission.60% Users of
 Memory consumption: 51.2 MB, At all C++ 71 were defeated in the submission.30% Users of