旋转盒子 图解题解

旋转加重力，最后要返回什么形状

给一个 m 行 n 列的字符箱子 box，井号是石头、星号是固定障碍物、点是空位。把整个箱子顺时针转 90 度，重力立刻生效，石头垂直下落，直到压在障碍物、别的石头或箱子底部才停，障碍物钉死不动。题面例子是 2 行 4 列，转完要返回 4 行 2 列——行列尺寸从 m 行 n 列换成 n 行 m 列，这点先记牢。

真把图转过来再一格格往下砸，累在哪

先真把矩阵转出来、再让每颗石头一格格往下砸，是最贴题意的走法：扫一遍网格，石头正下方是空位就挪它下去一格，一趟到不了底就再扫，直到整张图不再变。它能算对，可一颗石头最坏落 n 格、每趟又要扫全图，掉到底可能要 O(n) 趟，合起来奔着 O(m·n·max(m,n)) 去，反复扫到稳定的退出条件也容易写错。

凭什么旋转前就敢让石头先向右靠拢

绕开反复下落，靠的是把旋转和重力拆开看。顺时针转 90 度会把方向也一起转过去：原图里的向右，转完恰好对应新图里的向下。既然如此，与其转完再让石头往下掉，不如旋转前就在原图每行里让石头向右靠拢到位，再把靠好的图整体转过去，两种顺序落点完全一样。重力就这样被提前化成每行向右滑这件一维小事，剩下的旋转只是纯粹搬格子。

每行怎么靠拢，障碍物把它切成几段

障碍物是死挡板，把一行切成几段互不相通的区间，石头只能在自己那段里滑、穿不过障碍物到隔壁段。于是从这行最右端往左扫，把遇到的空位记成落脚点：扫到障碍物，攒的落脚点全部清空，因为它右边的空位帮不了左边的石头；扫到石头，右侧同段还留着落脚点就滑过去占最靠右那个、腾出的空位再补回，同段没有则不动。参考代码用一个队列 deque 存空位下标、从队头取最靠右的；换个写指针从右往左原地摆放也一样。

题面那个 2 行 4 列箱子，两步各走出什么

拿题面的 box=[["#",".","*","."],["#","#","*","."]] 走两步。先靠拢：行 0 = ["#",".","*","."]，障碍物在第 2 列，把这行切成第 0-1 列与第 3 列两段；左段第 0 列的石头向右滑一格到第 1 列，行 0 成 [".","#","*","."]。行 1 = ["#","#","*","."] 的两颗石头本就贴着障碍物、无处可滑，整行不动。

再旋转：顺时针转 90 度，底行行 1 竖成结果最左列，顶行行 0 竖成最右列。左列自上而下是石头、石头、障碍物、空位；右列是空位、石头、障碍物、空位。两列并起来就是 [["#","."],["#","#"],["*","*"],[".","."]]，和题面答案一致。

O(m·n) 之外，单行和空行别漏想

每个格子在旋转拷贝时搬一次、靠拢时入队出队常数次，时间 O(m·n)，至少得读遍所有格子，已是下界；答案矩阵占 O(m·n)，另加存空位下标的队列 O(max(m,n))。只有一行也不特殊，靠拢在这行内做完再竖过来；整行没石头就只旋转、不移动；石头贴着右墙或障碍物、同段无落脚点就留在原地。真正坑人的是结果尺寸：转完是 n 行 m 列而非 m 行 n 列，新数组得按行列互换后的形状开，沿用原尺寸会越界。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def rotateTheBox(self, boxGrid: List[List[str]]) -> List[List[str]]:
        m, n = len(boxGrid), len(boxGrid[0])
        ans = [[None] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                ans[j][m - i - 1] = boxGrid[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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int m = boxGrid.size(), n = boxGrid[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] = boxGrid[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;
    }
};

Java

import java.util.*;
class Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length, n = boxGrid[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] = boxGrid[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;
    }
}