Xoay ma trận
Đề bài
Cho ma trận $n \times n$ gồm các phần tử nguyên, hãy xoay ma trận 90 độ theo chiều kim đồng hồ.
Input:
- Dòng đầu tiên gồm số nguyên $n$.
- $n$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên, thể hiện ma trận.
Output: in ra ma trận đã cho sau khi xoay.
Điều kiện: $1 \le n \le 50$; $1 \le A_i \le 100$.
3
1 2 3
4 5 6
7 8 97 4 1
8 5 2
9 6 3Giải thích ví dụ: xoay 90° theo chiều kim đồng hồ thì hàng trên cùng 1 2 3 "ngã" sang bên phải thành cột cuối cùng (đọc từ trên xuống: 1, 2, 3); hàng dưới cùng 7 8 9 thành cột đầu tiên. Đọc lại theo từng hàng ta được 7 4 1 / 8 5 2 / 9 6 3.
Lời mở đầu
Xoay ma trận là bài kinh điển để luyện khả năng biến đổi chỉ số trên mảng 2 chiều: ô $(i, j)$ đi đâu sau khi xoay? Nghĩ ra được công thức thì code chỉ vài dòng; nghĩ sai thì rất dễ xoay ngược chiều mà ví dụ nhìn qua vẫn "na ná". Mình sẽ trình bày 3 cách: dùng mảng phụ theo công thức, in trực tiếp không cần mảng phụ, và xoay tại chỗ bằng "chuyển vị + lật" – một mẹo rất hay gặp trong phỏng vấn.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, đề không chia subtask. Mình chia theo độ lớn thành 3 nhóm:
| Test | n | Giá trị phần tử |
|---|---|---|
| 1 – 30 | 3 … 10 | 1 … 100 |
| 31 – 80 | 5 … 50 | 1 … 100 |
| 81 – 100 | 50 … 50 | 1 … 100 |
- Không có test nào với $n = 1$ hay $n = 2$, $n$ nhỏ nhất là 3 (chính là test ví dụ ở test 1). Các nhóm 1, 2 có cả $n$ chẵn và lẻ – với $n$ lẻ có một ô ở chính giữa đứng yên khi xoay.
- Mọi phần tử nằm trong $[1, 100]$ đúng như đề, phần tử lặp lại rất nhiều nên phải in đúng vị trí, không "ăn may" được.
- Ma trận lớn nhất chỉ $50 \times 50 = 2500$ số nên mọi cách $O(n^2)$ đều chạy tức thì.
| Mức | Điều kiện | Test | Cách 1 | Cách 2 | Cách 3 |
|---|---|---|---|---|---|
| 1 | $n \le 10$ | 1 – 30 | ✔ | ✔ | ✔ |
| 2 | $5 \le n \le 50$ ngẫu nhiên | 31 – 80 | ✔ | ✔ | ✔ |
| 3 | $n = 50$ | 81 – 100 | ✔ | ✔ | ✔ |
Ý tưởngÔ (i, j) đi đâu sau khi xoay?
Đánh số hàng, cột từ 1. Khi xoay 90° theo chiều kim đồng hồ:
- Hàng 1 (trên cùng) trở thành cột $n$ (bên phải cùng), hàng 2 thành cột $n - 1$, …, hàng $i$ thành cột $n + 1 - i$.
- Trong một hàng, phần tử bên trái ($j$ nhỏ) sau khi "ngã" sang phải sẽ nằm trên: phần tử ở cột $j$ thành phần tử ở hàng $j$.
Kiểm tra với ví dụ: $a[1][1] = 1$ đi tới $b[1][3]$ (góc trên phải), $a[3][1] = 7$ đi tới $b[1][1]$ (góc trên trái). Đúng như output 7 4 1 ở hàng đầu.
Em nhập ma trận (các hàng cách nhau dấu phẩy) rồi bấm Tiếp để xem từng hàng "ngã" thành cột. Mỗi ô có ghi toạ độ gốc bé ở góc và tô màu theo hàng gốc:
Cách 1Mảng phụ theo công thức
Dùng thêm mảng b, duyệt mọi ô của a và đặt vào đúng chỗ b[j][n + 1 - i], cuối cùng in b.
- Vì đánh số từ 1 nên cột đích là
n + 1 - i. Nếu đánh số từ 0 (như bản Python) thì công thức thànhb[j][n - 1 - i] = a[i][j]. - Mảng khai báo
[55][55]toàn cục là đủ cho $n \le 50$ và tự được khởi tạo bằng 0.
Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất 0.006 giây. Python đúng 100/100 test, test chậm nhất 0.026 giây.
Cách 2In trực tiếp, không cần mảng phụ
Đề chỉ yêu cầu in ra ma trận sau khi xoay, nên ta không cần thật sự tạo ra nó. Theo công thức $b[i][j] = a[n + 1 - j][i]$: hàng $i$ của kết quả là cột $i$ của a đọc từ dưới lên. Vậy chỉ cần 2 vòng lặp: $i$ chạy theo cột của a, $j$ chạy từ $n$ về 1 theo hàng.
Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất 0.003 giây. Python đúng 100/100 test, test chậm nhất 0.024 giây.
j từ $n$ về 1 và in a[i][j] với i từ 1 đến $n$ (in các cột từ phải sang trái, mỗi cột đọc từ trên xuống) thì ma trận bị xoay ngược chiều kim đồng hồ: ví dụ ra 3 6 9 / 2 5 8 / 1 4 7. Mình đã nộp thử phiên bản sai này lên bộ test: 0/100 test đúng – không ăn được test nào, kể cả test ví dụ. Vì vậy luôn kiểm tra lại công thức bằng 1–2 ô ở góc trước khi code nhé.
for(int j = n; j >= 1; j--){ // SAI: các cột từ phải sang trái
for(int i = 1; i <= n; i++) cout << a[i][j] << " "; // mỗi cột đọc từ trên xuống
cout << "\n";
}Cách 3Xoay tại chỗ: chuyển vị rồi lật
Nếu đề bắt phải biến đổi ngay trên mảng a (không được dùng mảng phụ – ví dụ để dùng tiếp cho các thao tác khác), ta tách phép xoay thành 2 phép "lật" đơn giản:
Bước 2 – đảo ngược từng hàng (lật trái ↔ phải): $a''[i][j]$ $= a'[i][n + 1 - j]$ $= a[n + 1 - j][i]$ – đúng bằng công thức xoay!
Ở bước 1, chỉ duyệt $j > i$ (nửa trên đường chéo). Nếu duyệt mọi cặp $(i, j)$ thì mỗi cặp bị đổi 2 lần và ma trận quay về như cũ – một lỗi rất hay gặp. Em bấm Tiếp để xem 2 bước lật:
Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất 0.004 giây. Python đúng 100/100 test, test chậm nhất 0.024 giây.
Mẹo nhớ: chuyển vị rồi đảo từng hàng → xoay theo chiều kim đồng hồ; chuyển vị rồi đảo thứ tự các hàng (lật trên ↔ dưới) → xoay ngược chiều kim đồng hồ. Xoay 180° = đảo thứ tự hàng rồi đảo từng hàng.
Nhận xét
Đăng nhận xét