Question

1861. 旋转盒子

English Version

题目描述

给你一个 m x n 的字符矩阵 box ，它表示一个箱子的侧视图。箱子的每一个格子可能为：

• '#' 表示石头
• '*' 表示固定的障碍物
• '.' 表示空位置

这个箱子被 顺时针旋转 90 度 ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力 不会 影响障碍物的位置，同时箱子旋转不会产生惯性 ，也就是说石头的水平位置不会发生改变。

题目保证初始时 box 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。

请你返回一个_ _n x m的矩阵，表示按照上述旋转后，箱子内的结果。

 

示例 1：

输入：box = [["#",".","#"]]
输出：[["."],
    ["#"],
    ["#"]]

示例 2：

输入：box = [["#",".","*","."],
        ["#","#","*","."]]
输出：[["#","."],
    ["#","#"],
    ["*","*"],
    [".","."]]

示例 3：

输入：box = [["#","#","*",".","*","."],
        ["#","#","#","*",".","."],
        ["#","#","#",".","#","."]]
输出：[[".","#","#"],
    [".","#","#"],
    ["#","#","*"],
    ["#","*","."],
    ["#",".","*"],
    ["#",".","."]]

 

提示：

• m == box.length
• n == box[i].length
• 1 <= m, n <= 500
• box[i][j] 只可能是 '#' ，'*' 或者 '.' 。

解法

方法一：队列模拟

我们先将矩阵顺时针旋转 90 度，然后模拟每一列石头的下落过程。

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

class Solution:
  def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
    m, n = len(box), len(box[0])
    ans = [[None] * m for _ in range(n)]
    for i in range(m):
      for j in range(n):
        ans[j][m - i - 1] = box[i][j]
    for j in range(m):
      q = deque()
      for i in range(n - 1, -1, -1):
        if ans[i][j] == '*':
          q.clear()
        elif ans[i][j] == '.':
          q.append(i)
        elif q:
          ans[q.popleft()][j] = '#'
          ans[i][j] = '.'
          q.append(i)
    return ans

class Solution {
  public char[][] rotateTheBox(char[][] box) {
    int m = box.length, n = box[0].length;
    char[][] ans = new char[n][m];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans[j][m - i - 1] = box[i][j];
      }
    }
    for (int j = 0; j < m; ++j) {
      Deque<Integer> q = new ArrayDeque<>();
      for (int i = n - 1; i >= 0; --i) {
        if (ans[i][j] == '*') {
          q.clear();
        } else if (ans[i][j] == '.') {
          q.offer(i);
        } else if (!q.isEmpty()) {
          ans[q.pollFirst()][j] = '#';
          ans[i][j] = '.';
          q.offer(i);
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
    int m = box.size(), n = box[0].size();
    vector<vector<char>> ans(n, vector<char>(m));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans[j][m - i - 1] = box[i][j];
      }
    }
    for (int j = 0; j < m; ++j) {
      queue<int> q;
      for (int i = n - 1; ~i; --i) {
        if (ans[i][j] == '*') {
          queue<int> t;
          swap(t, q);
        } else if (ans[i][j] == '.') {
          q.push(i);
        } else if (!q.empty()) {
          ans[q.front()][j] = '#';
          q.pop();
          ans[i][j] = '.';
          q.push(i);
        }
      }
    }
    return ans;
  }
};

func rotateTheBox(box [][]byte) [][]byte {
  m, n := len(box), len(box[0])
  ans := make([][]byte, n)
  for i := range ans {
    ans[i] = make([]byte, m)
  }
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      ans[j][m-i-1] = box[i][j]
    }
  }
  for j := 0; j < m; j++ {
    q := []int{}
    for i := n - 1; i >= 0; i-- {
      if ans[i][j] == '*' {
        q = []int{}
      } else if ans[i][j] == '.' {
        q = append(q, i)
      } else if len(q) > 0 {
        ans[q[0]][j] = '#'
        q = q[1:]
        ans[i][j] = '.'
        q = append(q, i)
      }
    }
  }
  return ans
}