Cyclically Rotating a Grid (LeetCode 1914)

Nguồn: LeetCode 1914 Độ khó: Trung bình (Medium) Mô phỏng Mảng 2 chiều Chia lấy dư

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

1914. Cyclically Rotating a Grid – Xoay vòng bảng số (LeetCode, độ khó Medium)

Cho một ma trận số nguyên grid kích thước $m \times n$, trong đó $m$ và $n$ đều là số chẵn, và một số nguyên $k$.

Ma trận được tạo thành từ nhiều lớp như hình dưới, mỗi màu là một lớp:

Ma trận $6 \times 6$ gồm 3 lớp (hình minh hoạ do mình vẽ lại theo ý hình của đề gốc).

Một lần xoay vòng ma trận được thực hiện bằng cách xoay vòng từng lớp của ma trận. Để xoay vòng một lớp một lần, mỗi phần tử trong lớp sẽ chiếm chỗ của phần tử kề với nó theo hướng ngược chiều kim đồng hồ. Ví dụ một lần xoay:

40	10
30	20

⟶

10	20
40	30

Mỗi số dịch sang ô kề theo chiều ngược kim đồng hồ: 40 đi xuống, 30 sang phải, 20 đi lên, 10 sang trái.

Hãy trả về ma trận sau khi thực hiện $k$ lần xoay vòng.

Ràng buộc:

• $m =$ grid.length, $n =$ grid[i].length
• $2 \le m, n \le 50$
• Cả $m$ và $n$ đều là số chẵn.
• $1 \le$ grid[i][j] $\le 5000$
• $1 \le k \le 10^9$

Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm rotateGrid trong class Solution. Để chạy như một chương trình bình thường (và dùng khung chạy tay bên dưới), mình đặt thêm định dạng:

• Dữ liệu vào: dòng đầu gồm 3 số nguyên $m, n, k$ (số dòng, số cột, số lần xoay); $m$ dòng tiếp theo, mỗi dòng $n$ số nguyên là một hàng của grid.
• Kết quả: $m$ dòng, mỗi dòng $n$ số cách nhau một dấu cách – ma trận sau khi xoay.

Ví dụ 1

Input: grid = [[40,10],[30,20]],
       k = 1
Output: [[10,20],[40,30]]
---stdin---
2 2 1
40 10
30 20
---stdout---
10 20
40 30

Hai hình ở trên chính là ma trận trước và sau lần xoay.

Ví dụ 2

Input: grid = [[1,2,3,4],[5,6,7,8],
               [9,10,11,12],[13,14,15,16]],
       k = 2
Output: [[3,4,8,12],[2,11,10,16],
         [1,7,6,15],[5,9,13,14]]
---stdin---
4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
---stdout---
3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

Ma trận được xoay 2 lần (xem giải thích ở phần Lời mở đầu).

1914. Cyclically Rotating a Grid (LeetCode, Medium)

You are given an m x n integer matrix grid, where m and n are both even integers, and an integer k.

The matrix is composed of several layers, which is shown in the below image, where each color is its own layer: (image – see the colored figure in the Vietnamese tab)

A cyclic rotation of the matrix is done by cyclically rotating each layer in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the counter-clockwise direction. An example rotation is shown below: (image)

Return the matrix after applying k cyclic rotations to it.

Example 1:

Input: grid = [[40,10],[30,20]], k = 1
Output: [[10,20],[40,30]]
Explanation: The figures above represent the grid at every state.

Example 2:

Input: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
Output: [[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
Explanation: The figures above represent the grid at every state.

Constraints:

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• Both m and n are even integers.
• 1 <= grid[i][j] <= 5000
• 1 <= k <= 10^9

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.

Giải thích ví dụ 2 cho bạn nào chưa hiểu đề: ma trận $4 \times 4$ có 2 lớp – lớp ngoài gồm 12 số, lớp trong gồm 4 số $6, 7, 11, 10$. Mỗi lần xoay, cả hai lớp cùng "trượt" một ô theo chiều ngược kim đồng hồ (cột trái đi xuống, hàng dưới sang phải, cột phải đi lên, hàng trên sang trái):

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Ban đầu

⟶

2	3	4	8
1	7	11	12
5	6	10	16
9	13	14	15

Sau 1 lần

⟶

3	4	8	12
2	11	10	16
1	7	6	15
5	9	13	14

Sau 2 lần

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Xoay từng bước, đủ k lần · O(k·m·n) – TLECách 2Liệt kê viền + dịch k mod chu kỳ · O(m·n)

Cách 1Xoay từng bước, làm đủ k lần – O(k·m·n)

Làm đúng như đề mô tả: với mỗi lớp, lặp $k$ lần, mỗi lần dịch cả viền đi một ô ngược chiều kim đồng hồ (giữ lại số ở góc trên-trái, kéo hàng trên sang trái, cột phải lên trên, hàng dưới sang phải, cột trái xuống dưới, rồi đặt số đã giữ vào ô ngay dưới góc trên-trái).

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int n = (int) grid.size();
        int m = (int) grid[0].size();
        for (int u = 0, d = n - 1, l = 0, r = m - 1; u <= d && l <= r; u++, d--, l++, r--) {
            for (int step = 0; step < k; step++) {
                // xoay viền 1 bước ngược chiều kim đồng hồ
                int keep = grid[u][l];
                for (int j = l; j < r; j++) grid[u][j] = grid[u][j + 1];
                for (int i = u; i < d; i++) grid[i][r] = grid[i + 1][r];
                for (int j = r; j > l; j--) grid[d][j] = grid[d][j - 1];
                for (int i = d; i > u + 1; i--) grid[i][l] = grid[i - 1][l];
                grid[u + 1][l] = keep;
            }
        }
        return grid;
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> grid[i][j];
    Solution sol;
    vector<vector<int>> res = sol.rotateGrid(grid, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cout << res[i][j] << (j + 1 < m ? " " : "\n");
    }
    return 0;
}

import sys
from typing import List


class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        n, m = len(grid), len(grid[0])
        u, d, l, r = 0, n - 1, 0, m - 1
        while u <= d and l <= r:
            for _ in range(k):
                # xoay viền 1 bước ngược chiều kim đồng hồ
                keep = grid[u][l]
                for j in range(l, r):
                    grid[u][j] = grid[u][j + 1]
                for i in range(u, d):
                    grid[i][r] = grid[i + 1][r]
                for j in range(r, l, -1):
                    grid[d][j] = grid[d][j - 1]
                for i in range(d, u + 1, -1):
                    grid[i][l] = grid[i - 1][l]
                grid[u + 1][l] = keep
            u, d, l, r = u + 1, d - 1, l + 1, r - 1
        return grid


def main():
    data = sys.stdin.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])
    vals = list(map(int, data[3:3 + n * m]))
    grid = [vals[i * m:(i + 1) * m] for i in range(n)]
    res = Solution().rotateGrid(grid, k)
    print("\n".join(" ".join(map(str, row)) for row in res))


if __name__ == "__main__":
    main()

TLE vì k lên tới 10^9

Mỗi lần xoay tốn $O(m \cdot n)$ thao tác, nhân với $k = 10^9$ thì không thể chạy kịp. Mình thử bảng $50 \times 50$, $k = 10^9$: code C++ chạy hơn 20 giây vẫn chưa xong. Cách này chỉ dùng được khi $k$ nhỏ (và làm code đối chiếu).

Không gian$O(1)$

Thời gian$O(k \cdot m \cdot n)$

Cách 2Liệt kê viền theo chiều ngược kim đồng hồ + dịch k mod chu kỳ – O(m·n)

Phương pháp giải: Implementation (cài đặt).

Ta chỉ cần làm theo đề là ra. Tuy nhiên bạn sẽ rất dễ lâm vào tình cảnh "code rối" nếu như không suy xét cẩn thận trước khi code.

Ta đi theo từng lớp của bảng, vì bảng chia làm nhiều lớp, và mỗi lớp chỉ như là "viền" của một bảng con. Ta gọi viền của một lớp là phần bảng từ hàng $u$ đến hàng $d$, từ cột $l$ đến cột $r$. Viền lớn nhất là $u = 0, d = m - 1, l = 0, r = n - 1$ (chỉ số từ 0), viền tiếp theo là $u = 1, d = m - 2, l = 1, r = n - 2$, … Như vậy khi đã xét xong viền hiện tại, ta tăng $u$ lên 1, giảm $d$ đi 1, tăng $l$ lên 1 và giảm $r$ đi 1.

Ý chính

1. Liệt kê tọa độ các ô trên viền theo chiều ngược kim đồng hồ vào một mảng tạm a: cột trái từ trên xuống, hàng dưới từ trái sang (bỏ 2 góc), cột phải từ dưới lên, hàng trên từ phải sang (bỏ 2 góc).
2. Một lần xoay thì phần tử ở vị trí thứ $i$ trong a sẽ dời sang vị trí thứ $i + 1$ (vị trí cuối quay về vị trí 0).
3. Tuy $k$ rất lớn ($1 \le k \le 10^9$), nhưng việc dịch chuyển có tính chu kỳ: viền có $C$ phần tử thì sau $C$ lần dịch, các phần tử lại trở về như cũ. Do đó số lần dịch thật sự chỉ là $k \bmod C$.
4. Vậy phần tử tại tọa độ a[i] của bảng cũ sẽ được ghi vào tọa độ a[(i + k mod C) mod C] của bảng kết quả.

Ví dụ lớp ngoài của bảng $4 \times 4$: a = (0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3), (2,3), (1,3), (0,3), (0,2), (0,1) – đúng 12 ô, giá trị theo thứ tự đó là $1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2$. Với $k = 2$: số 1 ở vị trí 0 đi tới vị trí 2 là ô $(2, 0)$; số 3 ở vị trí 10 đi tới vị trí $12 \bmod 12 = 0$ là ô $(0, 0)$ – khớp với đáp án.

Các bạn nhập bảng rồi bấm Tiếp để xem từng lớp được liệt kê và dịch (số nhỏ ở góc ô là thứ tự trong mảng a):

m n k grid (từng hàng, cách nhau dấu ;)

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int n = (int) grid.size();
        int m = (int) grid[0].size();
        vector<vector<int>> res;
        res.resize(n);
        for (int i = 0; i < n; i++) {
            res[i].resize(m, 0);
        }
        for (int u = 0, d = n - 1, l = 0, r = m - 1; u <= d && l <= r; u++, d--, l++, r--) {
            vector<pair<int, int>> a;
            for (int i = u; i <= d; i++) {
                a.push_back(make_pair(i, l));
            }
            for (int i = l + 1; i <= r - 1; i++) {
                a.push_back(make_pair(d, i));
            }
            for (int i = d; i >= u; i--) {
                a.push_back(make_pair(i, r));
            }
            for (int i = r - 1; i >= l + 1; i--) {
                a.push_back(make_pair(u, i));
            }
            int sz = (int) a.size();
            int cycle = k % sz;
            for (int i = 0; i < sz; i++) {
                int x = a[i].first;
                int y = a[i].second;
                int nextx = a[(i + cycle) % sz].first;
                int nexty = a[(i + cycle) % sz].second;
                res[nextx][nexty] = grid[x][y];
            }
        }
        return res;
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> grid[i][j];
    Solution sol;
    vector<vector<int>> res = sol.rotateGrid(grid, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cout << res[i][j] << (j + 1 < m ? " " : "\n");
    }
    return 0;
}

import sys
from typing import List


class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        n, m = len(grid), len(grid[0])
        res = [[0] * m for _ in range(n)]
        u, d, l, r = 0, n - 1, 0, m - 1
        while u <= d and l <= r:
            a = []
            for i in range(u, d + 1):
                a.append((i, l))
            for i in range(l + 1, r):
                a.append((d, i))
            for i in range(d, u - 1, -1):
                a.append((i, r))
            for i in range(r - 1, l, -1):
                a.append((u, i))
            sz = len(a)
            cycle = k % sz
            for i in range(sz):
                x, y = a[i]
                nx, ny = a[(i + cycle) % sz]
                res[nx][ny] = grid[x][y]
            u, d, l, r = u + 1, d - 1, l + 1, r - 1
        return res


def main():
    data = sys.stdin.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])
    vals = list(map(int, data[3:3 + n * m]))
    grid = [vals[i * m:(i + 1) * m] for i in range(n)]
    res = Solution().rotateGrid(grid, k)
    print("\n".join(" ".join(map(str, row)) for row in res))


if __name__ == "__main__":
    main()

Giải thích một số chỗ trong code:

1. Trong code, n là số hàng và m là số cột (đặt tên theo thói quen của mình), các bạn đọc kỹ để khỏi nhầm với $m, n$ trong đề.
2. 4 vòng for liệt kê viền: cột trái lấy đủ từ hàng $u$ tới $d$, cột phải cũng lấy đủ từ $d$ về $u$, còn hàng dưới và hàng trên chỉ lấy phần giữa (cột $l + 1$ tới $r - 1$) để không lấy trùng 4 góc.
3. Ghi kết quả sang bảng mới res chứ không ghi đè lên grid, nhờ vậy không lo "đè mất" số chưa kịp dời.

Khung chạy tay (để dễ theo dõi, giới hạn $m, n \le 6$):

C++▶ Chạy tay từng dòng codeCách 2: với từng viền (u, d, l, r) liệt kê tọa độ ngược chiều kim đồng hồ vào a, rồi res[a[(i + k % sz) % sz]] = grid[a[i]].

Dữ liệu vào (stdin) – sửa thoải mái4 4 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4class Solution {

5public:

6 vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {

7 int n = (int) grid.size();

8 int m = (int) grid[0].size();

9 vector<vector<int>> res;

10 res.resize(n);

11 for (int i = 0; i < n; i++) {

12 res[i].resize(m, 0);

13 }

14 for (int u = 0, d = n - 1, l = 0, r = m - 1; u <= d && l <= r; u++, d--, l++, r--) {

15 vector<pair<int, int>> a;

16 for (int i = u; i <= d; i++) {

17 a.push_back(make_pair(i, l));

18 }

19 for (int i = l + 1; i <= r - 1; i++) {

20 a.push_back(make_pair(d, i));

21 }

22 for (int i = d; i >= u; i--) {

23 a.push_back(make_pair(i, r));

24 }

25 for (int i = r - 1; i >= l + 1; i--) {

26 a.push_back(make_pair(u, i));

27 }

28 int sz = (int) a.size();

29 int cycle = k % sz;

30 for (int i = 0; i < sz; i++) {

31 int x = a[i].first;

32 int y = a[i].second;

33 int nextx = a[(i + cycle) % sz].first;

34 int nexty = a[(i + cycle) % sz].second;

35 res[nextx][nexty] = grid[x][y];

36 }

37 }

38 return res;

39 }

40};

41

42int main() {

43 int n, m, k;

44 cin >> n >> m >> k;

45 vector<vector<int>> grid(n, vector<int>(m));

46 for (int i = 0; i < n; i++)

47 for (int j = 0; j < m; j++) cin >> grid[i][j];

48 Solution sol;

49 vector<vector<int>> res = sol.rotateGrid(grid, k);

50 for (int i = 0; i < n; i++) {

51 for (int j = 0; j < m; j++) cout << res[i][j] << (j + 1 < m ? " " : "\n");

52 }

53 return 0;

54}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: bảng kết quả res và mảng tạm a – $O(m \cdot n)$.
• Thời gian: mỗi ô của bảng được đưa vào a đúng một lần và được ghi sang res đúng một lần, không phụ thuộc $k$ – $O(m \cdot n)$.

Không gian$O(m \cdot n)$

Thời gian$O(m \cdot n)$

Ghi chú của mình: Code C++ và Python của cả 2 cách đã được kiểm tra với 2 ví dụ của đề (đều đúng) và 400 bộ test ngẫu nhiên (bảng chẵn tới $8 \times 8$, $k \le 60$), so giữa cách xoay từng bước và cách dịch theo chu kỳ – khớp hết. Với bảng $50 \times 50$, $k = 10^9$, Cách 2 C++ chạy khoảng 0.005 giây, Python khoảng 0.03 giây; còn Cách 1 C++ chạy hơn 20 giây vẫn chưa xong.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇