Các nhà nghiên cứu AI tại Đại học Szeged đang tổ chức một cuộc thi lập trình robot. Bạn của bạn, Hanga, quyết định tham gia. Mục tiêu là lập trình Pulibot tối thượng, với sự ngưỡng mộ dành cho trí thông minh tuyệt vời của Puli, giống chó chăn gia súc nổi tiếng của Hungary.

Pulibot được thử nghiệm trên mê cung gồm một lưới \((H+2)\times(W+2)\) ô. Các hàng được đánh số từ \(-1\) đến \(H\) theo hướng bắc–nam, các cột từ \(-1\) đến \(W\) theo hướng tây–đông. Ô ở hàng \(r\), cột \(c\) (\(-1\le r\le H\), \(-1\le c\le W\)) được gọi là ô \((r,c)\).

Với \(0\le r<H\) và \(0\le c<W\), ô \((r,c)\) có \(4\) ô liền kề:

• Ô \((r,c-1)\) ở phía tây.
• Ô \((r+1,c)\) ở phía nam.
• Ô \((r,c+1)\) ở phía đông.
• Ô \((r-1,c)\) ở phía bắc.

Ô \((r,c)\) là ô biên giới của mê cung nếu \(r=-1\), \(r=H\), \(c=-1\) hoặc \(c=W\). Mỗi ô không phải ô biên giới là ô chướng ngại vật hoặc ô trống. Mỗi ô trống có một màu, biểu diễn bằng số nguyên không âm từ \(0\) đến \(Z_{MAX}\), kể cả hai đầu. Ban đầu, mọi ô trống có màu \(0\).

Ví dụ, xét mê cung có \(H=4\), \(W=5\), với một ô chướng ngại vật \((1,3)\):

Ô chướng ngại vật duy nhất được đánh dấu bằng dấu chữ thập. Các ô biên giới được tô đậm. Số trong mỗi ô trống biểu diễn màu của ô đó.

Một đường đi có độ dài \(\ell\) (\(\ell>0\)) từ ô \((r_0,c_0)\) đến ô \((r_\ell,c_\ell)\) là dãy các ô trống đôi một khác nhau \((r_0,c_0),(r_1,c_1),\ldots,(r_\ell,c_\ell)\), trong đó với mỗi \(0\le i<\ell\), các ô \((r_i,c_i)\) và \((r_{i+1},c_{i+1})\) liền kề nhau.

Lưu ý rằng đường đi độ dài \(\ell\) chứa đúng \(\ell+1\) ô.

Các nhà nghiên cứu thiết lập một mê cung có ít nhất một đường đi từ \((0,0)\) đến \((H-1,W-1)\). Điều này đảm bảo hai ô \((0,0)\) và \((H-1,W-1)\) đều trống. Hanga không biết những ô nào trống và những ô nào là chướng ngại vật.

Nhiệm vụ của bạn là giúp Hanga lập trình Pulibot tìm một đường đi ngắn nhất, tức đường đi có độ dài nhỏ nhất, từ \((0,0)\) đến \((H-1,W-1)\) trong mê cung chưa biết trước. Thông số kỹ thuật của Pulibot và quy tắc cuộc thi được mô tả dưới đây.

Phần cuối của đề mô tả một công cụ hiển thị mà bạn có thể dùng để trực quan hóa Pulibot.

Thông số kỹ thuật của Pulibot

Với mỗi \(-1\le r\le H\) và \(-1\le c\le W\), trạng thái của ô \((r,c)\) là số nguyên được xác định như sau:

• Nếu là ô biên giới, trạng thái là \(-2\).
• Nếu là ô chướng ngại vật, trạng thái là \(-1\).
• Nếu là ô trống, trạng thái là màu của ô.

Chương trình của Pulibot thực hiện một dãy các bước. Trong mỗi bước, Pulibot nhận biết trạng thái các ô lân cận rồi thực hiện một lệnh được xác định bởi những trạng thái đó.

Giả sử đầu bước hiện tại, Pulibot ở ô trống \((r,c)\). Bước này được thực hiện như sau:

1. Pulibot nhận dạng mảng trạng thái hiện tại \(S=[S[0],S[1],S[2],S[3],S[4]]\), gồm trạng thái ô \((r,c)\) và mọi ô liền kề. \(S[0]\) là trạng thái ô \((r,c)\); \(S[1]\), \(S[2]\), \(S[3]\), \(S[4]\) lần lượt là trạng thái các ô phía tây, nam, đông, bắc.
2. Pulibot xác định lệnh \((Z,A)\) tương ứng với mảng trạng thái vừa nhận dạng.
3. Pulibot thực hiện lệnh: đặt màu ô \((r,c)\) thành \(Z\), rồi thực hiện hành động \(A\). Hành động này là ở lại ô \((r,c)\), di chuyển đến một trong \(4\) ô liền kề, hoặc kết thúc chương trình.

Ví dụ, xét tình huống bên trái hình sau. Pulibot ở ô \((0,0)\) có màu \(0\) và nhận dạng mảng \(S=[0,-2,2,2,-2]\). Chương trình có thể quy định rằng khi nhận dạng mảng này, Pulibot đặt màu ô hiện tại thành \(Z=1\) rồi di chuyển về phía đông, như ở giữa và bên phải hình:

Các quy tắc Cuộc thi Robot

• Ban đầu, Pulibot được đặt ở ô \((0,0)\) và bắt đầu thực hiện chương trình.
• Pulibot không được di chuyển đến ô không trống.
• Chương trình phải kết thúc sau tối đa \(500\,000\) bước.
• Sau khi chương trình kết thúc, phải tồn tại một đường đi ngắn nhất từ \((0,0)\) đến \((H-1,W-1)\) mà mọi ô trên đường đi có màu \(1\). Tất cả các ô trống khác phải có màu \(0\).
• Pulibot có thể kết thúc chương trình tại bất kỳ ô trống nào.

Ví dụ, hình sau mô tả một mê cung có \(H=W=6\). Cấu hình ban đầu ở bên trái và một cách tô màu hợp lệ sau khi kết thúc ở bên phải:

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

void program_pulibot();

• Hàm cần tạo chương trình của Pulibot. Chương trình này phải chạy đúng với mọi giá trị \(H\), \(W\) và mọi mê cung thỏa mãn các ràng buộc của bài toán.
• Hàm được gọi đúng một lần cho mỗi test.

Hàm này có thể gọi hàm sau để tạo chương trình của Pulibot:

void set_instruction(std::vector<int> S, int Z, char A);

• \(S\): mảng độ dài \(5\) mô tả một mảng trạng thái.
• \(Z\): số nguyên không âm biểu diễn một màu.
• \(A\): một ký tự biểu diễn hành động theo bảng sau.

Ký tự	Hành động
H	Ở lại.
W	Di chuyển về phía tây.
S	Di chuyển về phía nam.
E	Di chuyển về phía đông.
N	Di chuyển về phía bắc.
T	Kết thúc chương trình.

Lời gọi này hướng dẫn Pulibot thực hiện lệnh \((Z,A)\) khi nhận dạng mảng trạng thái \(S\).

Gọi hàm nhiều lần với cùng một mảng trạng thái \(S\) sẽ nhận phản hồi Output isn't correct.

Không bắt buộc gọi set_instruction cho mọi mảng trạng thái \(S\) có thể có. Tuy nhiên, nếu Pulibot gặp mảng trạng thái chưa được đặt lệnh, bạn sẽ nhận phản hồi Output isn't correct.

Sau khi program_pulibot hoàn thành, trình chấm chạy chương trình của Pulibot trên một hoặc nhiều mê cung. Những lần chạy này không tính vào giới hạn thời gian của lời giải. Trình chấm không thích nghi: tập các mê cung trong mỗi test được xác định trước.

Nếu Pulibot vi phạm bất kỳ quy tắc nào của Cuộc thi Robot trước khi kết thúc chương trình, bạn sẽ nhận phản hồi Output isn't correct.

Ví dụ

Hàm program_pulibot có thể gọi set_instruction như sau:

set_instruction([0, -2, -1, 0, -2], 1, E)
set_instruction([0, 1, -1, 0, -2], 1, E)
set_instruction([0, 1, 0, -2, -2], 1, S)
set_instruction([0, -1, -2, -2, 1], 1, T)

Lời gọi	Lệnh cho mảng trạng thái \(S\)
1	Đặt màu thành \(1\) và di chuyển về phía đông.
2	Đặt màu thành \(1\) và di chuyển về phía đông.
3	Đặt màu thành \(1\) và di chuyển về phía nam.
4	Đặt màu thành \(1\) và kết thúc chương trình.

Xét tình huống \(H=2\), \(W=3\), với mê cung sau:

Với mê cung cụ thể này, chương trình chạy trong bốn bước. Các mảng trạng thái Pulibot nhận dạng và các lệnh nó thực hiện tương ứng chính xác với bốn lời gọi set_instruction ở trên, theo đúng thứ tự. Lệnh cuối kết thúc chương trình.

Hình sau mô tả mê cung trước mỗi bước trong bốn bước và các màu cuối cùng sau khi kết thúc:

Tuy nhiên, chương trình gồm \(4\) lệnh này có thể không tìm được đường đi ngắn nhất trong những mê cung hợp lệ khác. Vì vậy, nếu nộp, chương trình sẽ nhận phản hồi Output isn't correct.

Các ràng buộc

\(Z_{MAX}=19\). Do đó, Pulibot có thể dùng các màu từ \(0\) đến \(19\), kể cả hai đầu.

Với mỗi mê cung dùng để kiểm thử Pulibot:

• \(2\le H,W\le 15\).
• Có ít nhất một đường đi từ \((0,0)\) đến \((H-1,W-1)\).

Các subtask

Subtask	Điểm	Ràng buộc bổ sung
1	6	Không có ô chướng ngại vật trong mê cung.
2	10	\(H=2\).
3	18	Có đúng một đường đi giữa mỗi cặp ô trống.
4	20	Mỗi đường đi ngắn nhất từ \((0,0)\) đến \((H-1,W-1)\) có độ dài \(H+W-2\).
5	46	Không có ràng buộc nào thêm.

Nếu trong bất kỳ test nào, lời gọi set_instruction hoặc quá trình thực thi chương trình Pulibot không tuân theo các ràng buộc trong mục Chi tiết cài đặt, điểm của lời giải cho subtask đó là \(0\).

Trong mỗi subtask, bạn có thể đạt điểm thành phần bằng cách tạo một cách tô màu gần đúng. Cụ thể:

• Lời giải của một test là đầy đủ nếu cách tô màu cuối cùng của các ô trống thỏa mãn các quy tắc Cuộc thi Robot.
• Lời giải của một test là một phần nếu cách tô màu cuối cùng thỏa mãn tất cả điều kiện sau: tồn tại một đường đi ngắn nhất từ \((0,0)\) đến \((H-1,W-1)\) mà mọi ô trên đường đi có màu \(1\); không có ô trống nào khác trong lưới có màu \(1\); có ô trống trong lưới mang màu khác \(0\) và \(1\).

Nếu lời giải cho một test không phải đầy đủ hay một phần, điểm của test đó là \(0\).

Trong các subtask \(1\)–\(4\), lời giải đầy đủ được \(100\%\) và lời giải một phần cho một test được \(50\%\) số điểm của subtask đó.

Trong subtask \(5\), điểm phụ thuộc vào số màu dùng trong chương trình Pulibot. Cụ thể, gọi \(Z^\star\) là giá trị lớn nhất của \(Z\) trong tất cả các lời gọi set_instruction. Điểm của test được tính theo bảng sau:

Điều kiện	Điểm đầy đủ	Điểm một phần
\(11\le Z^\star\le 19\)	\(20+(19-Z^\star)\)	\(12+(19-Z^\star)\)
\(Z^\star=10\)	31	23
\(Z^\star=9\)	34	26
\(Z^\star=8\)	38	29
\(Z^\star=7\)	42	32
\(Z^\star\le 6\)	46	36

Điểm của mỗi subtask là điểm nhỏ nhất trong các test thuộc subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: H W
dòng 2 + r (0 ≤ r < H): m[r][0] m[r][1] … m[r][W − 1]

Ở đây, \(m\) là mảng gồm \(H\) mảng, mỗi mảng có \(W\) số nguyên, mô tả các ô không phải ô biên giới. \(m[r][c]=0\) nếu ô \((r,c)\) trống và \(m[r][c]=1\) nếu đó là ô chướng ngại vật.

Trình chấm mẫu trước tiên gọi program_pulibot(). Nếu phát hiện vi phạm giao thức, trình chấm in Protocol Violation: <MSG> rồi kết thúc, trong đó <MSG> là một trong các thông báo sau:

• Invalid array: điều kiện \(-2\le S[i]\le Z_{MAX}\) không thỏa mãn với một \(i\) nào đó, hoặc độ dài \(S\) khác \(5\).
• Invalid color: điều kiện \(0\le Z\le Z_{MAX}\) không thỏa mãn.
• Invalid action: ký tự \(A\) không thuộc H, W, S, E, N, T.
• Same state array: set_instruction được gọi với cùng mảng \(S\) ít nhất hai lần.

Nếu không, sau khi program_pulibot hoàn thành, trình chấm mẫu thực thi chương trình Pulibot trên mê cung trong dữ liệu vào.

Trình chấm mẫu tạo hai kết quả ra. Thứ nhất, trình chấm ghi nhật ký các hành động của Pulibot vào tệp robot.bin trong thư mục làm việc. Tệp này là dữ liệu vào cho công cụ trực quan hóa được mô tả ở phần sau.

Thứ hai, nếu chương trình Pulibot không kết thúc thành công, trình chấm mẫu in một trong các thông báo sau:

• Unexpected state: Pulibot nhận dạng một mảng trạng thái chưa được dùng trong lời gọi set_instruction.
• Invalid move: một hành động khiến Pulibot di chuyển đến ô không trống.
• Too many steps: Pulibot đã thực hiện \(500\,000\) bước mà chưa kết thúc chương trình.

Nếu không, gọi \(e[r][c]\) là trạng thái ô \((r,c)\) sau khi chương trình kết thúc. Trình chấm mẫu in \(H\) dòng theo định dạng:

dòng 1 + r (0 ≤ r < H): e[r][0] e[r][1] … e[r][W − 1]

Công cụ hiển thị

Gói đính kèm của bài toán có tệp display.py. Khi được gọi, chương trình Python này hiển thị các hành động của Pulibot trong mê cung được mô tả bởi dữ liệu vào của trình chấm mẫu. Để thực hiện điều này, tệp nhị phân robot.bin phải có trong thư mục làm việc.

Để gọi chương trình, chạy lệnh sau:

python3 display.py

Một giao diện đồ họa đơn giản sẽ xuất hiện, với các tính năng chính sau:

• Quan sát trạng thái toàn bộ mê cung. Vị trí hiện tại của Pulibot được đánh dấu bằng hình chữ nhật.
• Duyệt qua các bước của Pulibot bằng nút mũi tên hoặc phím nóng tương ứng. Bạn cũng có thể chuyển đến một bước cụ thể.
• Bước tiếp theo được hiển thị ở phía dưới, gồm mảng trạng thái hiện tại và lệnh sẽ thực hiện. Sau bước cuối, giao diện hiển thị một thông báo lỗi của trình chấm hoặc Terminated nếu chương trình kết thúc thành công.
• Với mỗi số biểu diễn một màu, bạn có thể gán một màu nền trực quan và một văn bản hiển thị. Văn bản này là một xâu ngắn xuất hiện trong mỗi ô mang màu đó. Bạn có thể gán màu nền và văn bản bằng hộp thoại mở ra khi nhấn Colors, hoặc bằng cách chỉnh sửa tệp colors.txt.
• Dùng nút Reload để tải lại robot.bin. Điều này hữu ích khi nội dung tệp đã thay đổi.

---

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.