Caro

Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều Độ khó: Dễ Mảng 2 chiều Duyệt 4 hướng

Đề bài

Tí và Tèo đang chơi trò chơi caro, Tí đi quân 'x' và Tèo đi quân 'o' vào các ô vuông trên bàn cờ. Ai đi được 5 ký hiệu liên tiếp (theo đường dọc, hoặc đường ngang, hoặc đường chéo) trước thì thắng. Giả sử bàn cờ là một hình vuông kích thước $n \times n$. Cho tình trạng của một bàn cờ, bạn hãy cho biết giữa Tí và Tèo có người thắng hay chưa, hay ván cờ vẫn đang tiếp diễn.

Dữ liệu nhập:

• Dòng đầu tiên là số nguyên $n$ $(5 \le n \le 20)$ là kích thước bàn cờ.
• Trong $n$ dòng tiếp theo, mỗi dòng gồm $n$ ký tự biểu thị tình trạng bàn cờ. Mỗi ký tự là một trong ba giá trị 'x', 'o' và dấu chấm '.' (x và o viết thường, dấu chấm là ô chưa đánh).

Dữ liệu xuất:

• Nếu Tí thắng, in ra dòng chữ Ti wins. Nếu Tèo thắng, in ra dòng chữ Teo wins (Tí Tèo không dấu).
• Nếu ván cờ vẫn đang tiếp diễn chưa có ai thắng, in ra dòng chữ Not yet (chú ý chữ hoa chữ thường).

Ghi chú: dữ liệu cho đảm bảo không có trường hợp 2 đấu thủ cùng thắng. Luật chơi cho phép chặn 2 đầu cũng thắng, liên tiếp nhiều hơn 5 quân cũng thắng.

Ví dụ 1 – input

5
xo...
.xo..
..xo.
...xo
....x

Ví dụ 1 – output

Ti wins

Ví dụ 2 – input

5
xo...
.xx..
ooooo
...xo
....x

Ví dụ 2 – output

Teo wins

Ví dụ 3 – input

5
ox...
.xoo.
..ox.
.o.xo
..x..

Ví dụ 3 – output

Not yet

Lời mở đầu

Đây là bài mở màn của chương Mảng 2 chiều: đọc một bàn cờ vào mảng 2 chiều rồi "đi dạo" trên đó theo các hướng. Bài không khó nhưng rất hay bị sai ở chỗ quên đường chéo phụ hoặc truy cập ra ngoài bàn cờ. Mình sẽ giải thích thật kỹ để các bạn nắm chắc kỹ thuật duyệt theo hướng – kỹ thuật này sẽ dùng lại ở rất nhiều bài sau trong chương.

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ộ test12 testÝ tưởng4 hướngCodeC++ & Python

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

Số test	Kích thước n	Ti wins	Teo wins	Not yet
12	5 (3 test), 7 (3 test), 10 (3 test), 15 (3 test)	4	4	4

Bài không chia subtask: $n$ tối đa chỉ 20 nên cách duyệt mọi ô, mọi hướng ở dưới chạy thoải mái cho toàn bộ test. Ba kết quả được chia đều nhau, nên code phải xử lý đúng cả trường hợp chưa ai thắng.

Ý tưởngMỗi ô là một điểm xuất phát, thử 4 hướng

Một dãy 5 quân liên tiếp luôn có một quân đầu tiên. Nếu ta đứng ở quân đầu tiên đó thì 4 quân còn lại nằm theo một trong các hướng:

• Ngang sang phải: $(0, +1)$
• Dọc xuống dưới: $(+1, 0)$
• Chéo chính xuống phải: $(+1, +1)$
• Chéo phụ xuống trái: $(+1, -1)$

Không cần xét thêm các hướng ngược lại (trái, lên, ...) vì dãy 5 quân đi ngược lại thì vẫn là dãy đó, chỉ là ta đứng ở quân cuối thay vì quân đầu. Vậy thuật toán là:

Thuật toán

Với mỗi ô $(i, j)$ và mỗi hướng $(dx, dy)$ trong 4 hướng trên, kiểm tra 5 ô $(i + k \cdot dx,\ j + k \cdot dy)$ với $k = 0..4$: tất cả phải nằm trong bàn cờ và cùng là quân c. Có một chỗ thoả mãn là quân c thắng.

Vì "liên tiếp nhiều hơn 5 quân cũng thắng" nên chỉ cần tìm thấy một đoạn đúng 5 quân là đủ (một dãy 6 quân chắc chắn chứa một đoạn 5 quân). Và "chặn 2 đầu cũng thắng" nên ta không phải quan tâm 2 đầu dãy có bị chặn hay không. Đề cũng đảm bảo không có chuyện cả 2 cùng thắng, nên kiểm tra x trước hay o trước đều được.

Em sửa bàn cờ rồi bấm Tiếp để xem máy "quét" từng ô, từng hướng:

Bàn cờ (mỗi dòng 1 hàng)

Ví dụ nhanh:

CodeCài đặt

Mình viết hàm check(i, j, dx, dy, c) kiểm tra 5 ô theo một hướng, và hàm win(c) duyệt mọi ô, mọi hướng. Hai mảng dx[], dy[] giúp viết 4 hướng gọn trong một vòng lặp thay vì chép 4 đoạn code gần giống nhau.

C++▶ Chạy tay từng dòng codeHàm check kiểm tra 5 ô theo 1 hướng, hàm win duyệt mọi ô × 4 hướng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Các bước dừng ở dòng if trong hàm check mỗi khi một hướng thất bại (ra ngoài bàn cờ hoặc gặp quân khác).

1. Điều kiện x < 0 || x >= n || y < 0 || y >= n phải đặt trước a[x][y] != c: nhờ toán tử || "ngắt mạch", khi ô đã ra ngoài bàn cờ thì máy không đọc a[x][y] nữa, tránh truy cập ngoài mảng.
2. Ngay khi gặp một ô sai là return false, không cần xét tiếp các ô còn lại của đoạn.
3. Mảng a[25][25] kiểu char, đọc mỗi dòng bằng cin >> a[i] là đọc được cả chuỗi $n$ ký tự (chuỗi không có dấu cách).

Không gian$O(n^2)$

Thời gian$O(n^2 \cdot 4 \cdot 5)$

Ghi chú của mình: bản C++ và bản Python đều đạt 12/12 test của bộ test chính thức trên CLUE OJ, mỗi test chạy dưới 0.05 giây.

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 😇