Ma trận xoắn ốc

Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều Độ khó: Dễ Mảng 2 chiều Mô phỏng

Đề bài

In ra ma trận xoắn ốc kích cỡ $n$ dòng và $m$ cột.

Ví dụ với ma trận 5 dòng 6 cột:

1 2 3 4 5 6
18 19 20 21 22 7
17 28 29 30 23 8
16 27 26 25 24 9
15 14 13 12 11 10

Dữ liệu nhập: một dòng gồm hai số nguyên $n, m$.

Dữ liệu xuất: in ra ma trận xoắn ốc.

Điều kiện: $1 \le n, m \le 100$.

Ví dụ – input

3 3

Ví dụ – output

1 2 3
8 9 4
7 6 5

Lời mở đầu

Ma trận xoắn ốc là bài "kinh điển" của chương mảng 2 chiều: điền các số $1, 2, 3, \dots, n \cdot m$ bắt đầu từ góc trên trái, đi sang phải, xuống dưới, sang trái, lên trên, rồi cuộn dần vào trong. Mình sẽ giới thiệu hai cách nghĩ rất khác nhau: cách thứ nhất xem như một con rắn bò và "đụng là rẽ phải", cách thứ hai bóc ma trận thành từng lớp vỏ hình chữ nhật. Cả hai đều chạy thật trên bộ test, và mình chỉ cho các bạn một lỗi rất hay gặp ở cách thứ hai khiến mất gần nửa số test.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

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

Bộ test100 test Ý tưởngrắn bò rẽ phải Cách 1mảng hướng Cách 2bóc từng lớp Lỗi sai51/100 test

Bộ testBộ test chính thức có gì?

Nhóm	Các test	$n$	$m$	Có $n = 1$ hoặc $m = 1$	Vuông $n = m$	Cách 1, 2	Bản lỗi
Nhỏ	1 – 30	1 … 10	1 … 10	4	1	30/30	14/30
Lớn	31 – 100	1 … 100	3 … 100	3	2	70/70	37/70

Đề không chia subtask. Bộ test tự tách thành 2 nhóm: 30 test đầu nhỏ ($n, m \le 10$, ví dụ đề $3 \times 3$ là test 1), 70 test sau lớn tới $100 \times 100$ (test cuối đúng $100 \times 100$). Có cả ma trận một hàng, một cột ($1 \times 4$, $9 \times 1$, $1 \times 79$...) và ma trận "dẹt" như $93 \times 3$ – đây là những test bắt lỗi ở các trường hợp biên. Vì $n \cdot m \le 10\,000$ nên mọi cách $O(n \cdot m)$ đều chạy tức thì; cái phân loại bài làm là xử lý đúng các trường hợp biên.

Ý tưởngCon rắn bò, đụng là rẽ phải

Tưởng tượng một con rắn đứng ở ô $(0, 0)$, mặt hướng sang phải. Mỗi bước nó ghi số tiếp theo vào ô đang đứng rồi định bò thẳng tới. Nếu ô phía trước ra ngoài ma trận hoặc đã có số thì nó rẽ phải (quay 90° theo chiều kim đồng hồ): phải → xuống → trái → lên → phải ... Cứ thế cho đến khi điền đủ $n \cdot m$ số.

Hai mảng hướng

Đặt 4 hướng theo đúng thứ tự rẽ phải: dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0} (phải, xuống, trái, lên). Rẽ phải chỉ là d = (d + 1) % 4.

Một cách nhìn khác: ma trận gồm các lớp vỏ lồng nhau (trong widget dưới đây mỗi lớp một màu). Con rắn đi hết lớp ngoài cùng rồi mới chui vào lớp trong. Cách nhìn này dẫn tới Cách 2.

Em nhập $n$, $m$ (tối đa 8) rồi bấm Tiếp hoặc Tự chạy để xem con rắn bò:

n = m =

Ví dụ nhanh:

Cách 1Mô phỏng con rắn với mảng hướng

Dùng giá trị 0 để đánh dấu ô chưa điền (các số điền vào đều $\ge 1$ nên không lẫn). Mỗi vòng lặp điền số v, tính ô phía trước (nx, ny); nếu ô đó không đi được thì rẽ phải và tính lại.

C++▶ Chạy tay từng dòng codeCách 1: con rắn điền số, gặp biên hoặc ô đã điền thì rẽ phải.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Điều kiện nx < 0 || nx >= n || ny < 0 || ny >= m đặt trước a[nx][ny] != 0 để không đọc ra ngoài mảng (toán tử || ngắt mạch).
Chỉ cần rẽ một lần: sau khi rẽ phải, ô mới luôn đi được (trừ khi đã điền xong số cuối cùng – lúc đó vòng lặp cũng kết thúc nên không sao).
Không cần xử lý riêng trường hợp $n = 1$ hay $m = 1$: con rắn tự rẽ đúng chỗ.

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

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

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0.05 giây; bản Python đúng 100/100 test, chậm nhất 0.22 giây.

Cách 2Bóc từng lớp vỏ với 4 biên

Giữ 4 biên của phần chưa điền: hàng trên top, hàng dưới bot, cột trái lef, cột phải rig. Mỗi vòng điền một lớp vỏ bằng 4 vòng for, mỗi cạnh xong thì co biên tương ứng vào trong:

Cạnh trên: hàng top, cột lef → rig, xong thì top++.
Cạnh phải: cột rig, hàng top → bot, xong thì rig--.
Cạnh dưới: hàng bot, cột rig → lef, xong thì bot--.
Cạnh trái: cột lef, hàng bot → top, xong thì lef++.

C++▶ Chạy tay từng dòng codeCách 2: mỗi vòng while điền một lớp vỏ bằng 4 cạnh, co 4 biên dần vào trong.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Thử "1 × 4 (một hàng)" để thấy hai lệnh if bỏ qua cạnh dưới và cạnh trái như thế nào.

Hai lệnh if(top <= bot) và if(lef <= rig) là chỗ quan trọng nhất: khi lớp trong cùng chỉ còn một hàng (hoặc một cột), sau khi đi cạnh trên thì không còn hàng nào cho cạnh dưới, phải bỏ qua – nếu không sẽ đi ngược lại và ghi đè lên chính hàng đó.
Mỗi ô được điền đúng một lần nên tổng thời gian là $O(n \cdot m)$, giống Cách 1, nhưng không cần kiểm tra "ô đã điền chưa".

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

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

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0.05 giây; bản Python đúng 100/100 test, chậm nhất 0.20 giây.

Lỗi hay gặpQuên kiểm tra lớp chỉ còn một hàng/cột

Bỏ hai lệnh if ở Cách 2: chỉ đúng 51/100 test

Mình bỏ if(top <= bot) và if(lef <= rig) (luôn đi đủ 4 cạnh) rồi chấm lại. Với $n = 1, m = 4$: cạnh trên điền 1 2 3 4, cạnh phải không có ô nào, nhưng cạnh dưới lại chạy trên chính hàng 0 từ phải sang trái và ghi đè thành 7 6 5 4. Với $3 \times 7$, lớp trong cùng là hàng giữa 17 … 21, cũng bị ghi đè tương tự. Kết quả: sai 49 test, và tất cả các test sai đều có $\min(n, m)$ lẻ – đúng là các ma trận mà lớp trong cùng chỉ còn một hàng hoặc một cột.

Cách 1 (con rắn) không bị lỗi này vì nó tự nhìn thấy ô đã điền và rẽ. Đó là lý do mình thích Cách 1 khi đi thi: ít trường hợp đặc biệt phải nghĩ.

Ghi chú của mình: cả 2 cách (C++ và Python) đều đạt 100/100 test, test lớn nhất $100 \times 100$ chạy dưới 0.05 giây với C++ và khoảng 0.2 giây với Python. Bản Cách 2 bỏ quên hai lệnh if chỉ đạt 51/100 test.

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 😇

Lập Trình Thuật Toán