Repository navigation
Expand file tree
/
Copy pathRotatingTheBox.cpp
More file actions
95 lines (92 loc) · 2.87 KB
/
Copy pathRotatingTheBox.cpp
File metadata and controls
95 lines (92 loc) · 2.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// Source : https://leetcode.com/problems/rotating-the-box/
// Author : Hao Chen
// Date : 2021-05-22
/*****************************************************************************************************
*
* 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 '.'.
******************************************************************************************************/
class Solution {
public:
void rotate(vector<vector<char>>& src, vector<vector<char>>& dest) {
int m = src.size();
for(int row=0; row<dest.size(); row++) {
for(int col=0; col<dest[row].size(); col++) {
dest[row][col] = src[m-col-1][row];
}
}
}
void gravity(vector<vector<char>>& box) {
int m = box.size();
int n = box[0].size();
for(int col=0; col<n; col++) {
int bottom = m - 1;
for(int row=m-1; row>=0; row-- ) {
if (box[row][col] == '#') {
box[row][col] = '.';
box[bottom][col] = '#';
bottom--;
}else if (box[row][col] == '*') {
bottom = row-1;
}
}
}
}
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int row = box.size();
int col = box[0].size();
vector<vector<char>> result(col, vector<char>(row,'.'));
rotate(box, result);
gravity(result);
return result;
}
};