2048

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

Đề bài

Chào hè, Lúi bắt đầu bập bõm tìm hiểu về code, cậu khoái nhất là việc tự làm ra được một game gì đó. Cậu bắt đầu với việc clone lại game 2048 thần thánh.

2048 là một game khá đơn giản. Bạn có một ma trận $4 \times 4$, mỗi ô là một luỹ thừa cơ số 2. Bạn có thể dùng bàn phím để di chuyển ma trận theo 1 trong 4 hướng: lên (U), xuống (D), trái (L) và phải (R). Mỗi lần di chuyển, các ô trên ma trận sẽ cùng di chuyển theo một hướng; các ô chỉ dừng lại khi gặp viền của ma trận hoặc gặp một ô có số khác với số của ô đó. Trường hợp gặp ô có cùng số thì 2 ô sẽ hợp thành 1, giá trị của ô mới bằng tổng của 2 ô cũ, và ô mới này không thể hợp nhất với các ô cùng giá trị khác nữa (trong lượt đó).

Bạn hãy giúp Lúi clone lại game này nhé.

Dữ liệu nhập:

• Dòng đầu tiên chứa 1 trong 4 ký tự biểu thị hướng di chuyển (L, U, R, D).
• Tiếp theo là một ma trận $4 \times 4$, mỗi phần tử là một số thuộc tập $\{0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024\}$. Số 0 biểu thị ô đó trống.

Dữ liệu xuất: ma trận $4 \times 4$ sau khi di chuyển.

Ví dụ 1 – input

R
0 2 2 2
4 8 16 16
2 2 2 2
0 2 4 4

Ví dụ 1 – output

0 0 2 4
0 4 8 32
0 0 4 4
0 0 2 8

Ví dụ 2 – input

L
0 2 2 2
4 8 16 16
2 2 2 2
0 2 4 4

Ví dụ 2 – output

4 2 0 0
4 8 32 0
4 4 0 0
2 8 0 0

Ví dụ 3 – input

D
0 2 4 8
2 2 4 8
2 4 8 8
8 4 8 8

Ví dụ 3 – output

0 0 0 0
0 0 0 0
4 4 8 16
8 8 16 16

Ví dụ 4 – input

U
0 2 4 8
2 2 4 8
2 4 8 8
8 4 8 8

Ví dụ 4 – output

4 4 8 16
8 8 16 16
0 0 0 0
0 0 0 0

Lời mở đầu

Ai từng chơi 2048 chắc đều thấy luật chơi rất "tự nhiên": vuốt một cái là các ô trôi về một phía, ô nào trùng số thì dính vào nhau. Nhưng khi bắt tay vào viết code mô phỏng thì mới thấy có mấy cái bẫy: ô 2 2 4 vuốt trái ra 4 4 chứ không phải 8, hay vuốt phải thì phải xử lý các ô bên phải trước... Bài này là bài tập rất hay để luyện mô phỏng trên mảng 2 chiều: mình sẽ đi từ cách mô phỏng "y như game thật" tới cách gọn hơn là đưa cả 4 hướng về một hàm xử lý dãy 4 số, kèm theo 2 lỗi sai mình chạy thật trên bộ test để các bạn thấy nó "mất điểm" cỡ nào.

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, 4 hướngÝ tưởngdồn 1 dãy 4 sốCách 1trượt từng ôCách 2hàm dồn dãyLỗi saichạy thử trên test

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

Số test	Kích thước	Giá trị vào	Giá trị ra lớn nhất
100	luôn $4 \times 4$	0 … 1024	2048

Vài con số đáng chú ý mình đếm được trên 100 test:

• 67 test có ma trận kín ô (không có số 0): không ô nào trượt được nếu không có gộp, nên kết quả phụ thuộc hoàn toàn vào luật gộp.
• 10 test có hai số bằng nhau bị ngăn bởi ô trống (kiểu 2 0 2) – vẫn phải gộp được.
• Kết quả có thể lên tới 2048 (gộp hai ô 1024), vẫn nằm thoải mái trong kiểu int.
• 3 test không có cặp nào gộp, trong đó 2 test ma trận giữ nguyên sau khi vuốt.

Subtask: đề không chia subtask và ma trận luôn $4 \times 4$, nên cách nào đúng cũng chạy tức thì. Điều thực sự phân loại các bài làm là hướng vuốt, vì mỗi hướng có thứ tự xử lý khác nhau. Mình chia bộ test theo hướng và chấm cả 2 cách đúng lẫn 2 bản sai hay gặp (xem phần Lỗi hay gặp):

Nhóm (theo hướng)	Số test	Cách 1	Cách 2	Lỗi A	Lỗi B
L – vuốt trái	30	30/30	30/30	21/30	30/30
R – vuốt phải	19	19/19	19/19	11/19	2/19
U – vuốt lên	19	19/19	19/19	13/19	19/19
D – vuốt xuống	32	32/32	32/32	24/32	1/32
Tổng	100	100/100	100/100	69/100	52/100

Ý tưởngMỗi hàng (cột) là một dãy 4 số độc lập

Quan sát đầu tiên: khi vuốt trái hay phải, các ô chỉ chạy trong hàng của nó, 4 hàng không ảnh hưởng gì đến nhau. Tương tự, vuốt lên hay xuống thì 4 cột độc lập với nhau. Vậy một nước đi chỉ là 4 lần xử lý một dãy 4 số.

Để khỏi phải nghĩ 4 trường hợp, mình luôn lấy dãy theo thứ tự từ viền phía đích đi ra: gọi dãy đó là $b_0, b_1, b_2, b_3$ với $b_0$ là ô sát viền mà các số đang trôi tới. Ví dụ vuốt phải (R) thì hàng 0 2 2 2 được đọc từ phải sang trái thành $b = (2, 2, 2, 0)$. Khi đó, với mọi hướng, việc cần làm đều là "dồn dãy $b$ về phía $b_0$":

Dồn một dãy về phía b₀

1. Bỏ các số 0, giữ nguyên thứ tự các số còn lại (vì ô trống không cản đường ai cả). Ví dụ $(2, 2, 2, 0) \to (2, 2, 2)$.
2. Gộp từ đầu dãy: xét lần lượt, nếu số đang xét bằng số ngay sau nó thì gộp thành một số gấp đôi và bỏ qua luôn số sau (nó đã bị "ăn"); ngược lại giữ nguyên. $(2, 2, 2) \to (4, 2)$.
3. Thêm số 0 vào cuối cho đủ 4 ô: $(4, 2, 0, 0)$, rồi ghi ngược lại vào hàng theo đúng thứ tự đã lấy ra: hàng thành 0 0 2 4.

Hai chi tiết quyết định đúng/sai nằm ở bước 2:

• Gộp từ phía đích trước: dãy 2 2 2 vuốt trái phải ra 4 2 (hai số 2 bên trái gộp), vuốt phải ra 2 4 (hai số 2 bên phải gộp).
• Số vừa gộp không gộp tiếp: 2 2 4 vuốt trái ra 4 4 chứ không phải 8; 2 2 2 2 ra 4 4 chứ không phải 8.

Em chọn hướng, nhập ma trận (16 số) rồi bấm Tiếp để xem từng hàng/cột được lấy ra, bỏ số 0, gộp và ghi lại như thế nào:

Hướng Ma trận (16 số)

Ví dụ nhanh:

Cách 1Mô phỏng y như game: trượt từng ô một

Cách "thật thà" nhất là làm đúng như những gì mắt mình thấy khi chơi: lần lượt lấy từng ô có số, cho nó trượt từng bước một theo hướng $(dx, dy)$ chừng nào ô phía trước còn trống. Khi dừng lại, nếu ô phía trước có cùng số và ô đó chưa được gộp trong lượt này thì gộp vào. Mảng gop[][] đánh dấu các ô vừa được gộp để chúng không "ăn" thêm ô nào nữa.

Thứ tự xét các ô rất quan trọng: ô gần viền phía đích phải được xử lý trước (vuốt phải thì xét cột 3 trước, rồi cột 2, 1, 0; vuốt xuống thì xét hàng 3 trước). Như vậy khi một ô trượt tới, các ô phía trước nó đã nằm yên ở vị trí cuối cùng.

C++▶ Chạy tay từng dòng codeCách 1: lần lượt cho từng ô trượt từng bước, gộp nếu gặp ô cùng số chưa gộp.

Dữ liệu vào (stdin) – sửa thoải máiR 0 2 2 2 4 8 16 16 2 2 2 2 0 2 4 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Ví dụ "2 2 4 vuốt trái" cho thấy vì sao cần mảng gop: ở hàng đầu, ô 4 vừa gộp không ăn tiếp ô 4 phía sau.

1. dx, dy: vuốt trái là $(0, -1)$, phải $(0, 1)$, lên $(-1, 0)$, xuống $(1, 0)$. Nhờ đó cả 4 hướng dùng chung một đoạn code.
2. Dòng int i = (dx == 1) ? 3 - p : p; và int j = (dy == 1) ? 3 - q : q; đảo thứ tự duyệt khi đi xuống/sang phải, để ô sát viền đích luôn được xét trước.
3. Hàm trong(x, y) kiểm tra ô còn nằm trong ma trận; đặt trước a[x + dx][y + dy] trong điều kiện && để không truy cập ra ngoài mảng.
4. Điều kiện gộp có thêm !gop[nx][ny]: ô đã gộp rồi thì không gộp nữa. Thiếu điều kiện này là sai ngay (xem phần lỗi hay gặp).

Không gian$O(1)$ – ma trận $4 \times 4$

Thời gian$O(4 \cdot 4 \cdot 4)$: mỗi ô trượt tối đa 3 bước

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0.03 giây; bản Python cũng đúng 100/100 test (khoảng 0.09 giây mỗi test, phần lớn là thời gian khởi động Python).

Cách 2Đưa 4 hướng về một hàm dồn dãy 4 số

Cách 1 đúng nhưng hơi "rối": vừa trượt vừa gộp vừa đánh dấu. Theo ý tưởng ở trên, mình tách bài thành hai phần rõ ràng:

• Hàm don(b) chỉ lo dồn một dãy 4 số về phía b[0]: bỏ số 0 → gộp từng cặp → thêm 0.
• Hàm main lo việc "lấy dãy ra" và "ghi dãy vào" theo hướng: với hàng/cột thứ t, phần tử b[k] lấy từ a[t][k] (L), a[t][3-k] (R), a[k][t] (U), a[3-k][t] (D).

C++▶ Chạy tay từng dòng codeCách 2: lấy từng hàng/cột ra dãy b theo hướng, gọi don(b) rồi ghi ngược lại.

Dữ liệu vào (stdin) – sửa thoải máiR 0 2 2 2 4 8 16 16 2 2 2 2 0 2 4 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Dòng 19 (chép r vào b) mình gộp 4 lần lặp thành 1 bước cho gọn.

1. Vòng gộp dùng k++ bên trong khi gộp được: số c[k+1] đã nhập vào c[k] nên phải nhảy qua nó. Đây chính là chỗ đảm bảo "số vừa gộp không gộp tiếp": sau khi gộp, ta xét tiếp từ c[k+2] và so nó với c[k+3], không bao giờ so với kết quả vừa gộp.
2. Mảng r khởi tạo toàn 0 nên phần cuối dãy tự động là ô trống.
3. Lấy ra và ghi vào dùng cùng một công thức chỉ số, nên không sợ ghi nhầm chỗ.

Không gian$O(1)$

Thời gian$O(4 \cdot 4)$: 4 dãy, mỗi dãy 4 số

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

Mẹo mở rộng

Hàm don làm việc với một dãy bất kỳ, nên nếu đề đổi sang bàn $n \times n$ thì chỉ cần thay số 4 bằng $n$. Đây là lợi thế lớn của việc "đưa bài 2 chiều về bài 1 chiều".

Lỗi hay gặpHai lỗi sai mình chạy thử trên bộ test

Mình cố tình sửa code Cách 1 thành 2 phiên bản sai rất hay gặp và chấm lại trên bộ test thật:

Lỗi A – quên đánh dấu ô đã gộp: chỉ đúng 69/100 test

Bỏ điều kiện !gop[nx][ny]:

if(trong(nx, ny) && a[nx][ny] == a[x][y]){   // thiếu !gop[nx][ny]

Hàng 2 2 4 0 vuốt trái: hai số 2 gộp thành 4, rồi số 4 phía sau trượt tới thấy ô 4 (vừa gộp) nên gộp tiếp ra 8 0 0 0. Đáp án đúng là 4 4 0 0. Bộ test có rất nhiều ma trận kín ô với các số liên tiếp gấp đôi nhau nên lỗi này mất gần 1/3 số test.

Lỗi B – duyệt sai thứ tự: chỉ đúng 52/100 test

Luôn duyệt từ hàng 0, cột 0 cho mọi hướng:

int i = p;   // đúng ra: (dx == 1) ? 3 - p : p
int j = q;   // đúng ra: (dy == 1) ? 3 - q : q

Với L và U thì thứ tự này vẫn đúng (ô gần viền đích được xét trước), nhưng với R và D thì ô xa viền được trượt trước, bị ô phía trước (chưa trượt) chặn lại. Ví dụ hàng 2 0 0 0 vuốt phải: cột 0 trượt tới cột 3 thì ổn, nhưng hàng 2 2 0 0 vuốt phải: số 2 ở cột 0 gộp ngay vào cột 1 thành 0 4 0 0 rồi trượt thành 0 0 0 4 – may mắn đúng; còn hàng 2 4 0 0 thì số 2 đứng yên vì bị số 4 chặn, kết quả 2 0 0 4 – sai. Bảng thống kê cho thấy lỗi này gần như sai trọn các test hướng R và D.

Ghi chú của mình: cả 2 cách (C++ và Python) đều đạt 100/100 test trên bộ test chính thức, mỗi test dưới 0.1 giây. Hai bản cố tình sai chỉ đạt 69/100 test và 52/100 test. Bài nhỏ nhưng bắt buộc phải cẩn thận đúng 2 chi tiết: thứ tự xử lý từ phía đích và mỗi ô chỉ gộp một lần.

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 😇