Ở miền nam Ontario, nhiều nông dân trồng ngô tạo ra mê cung bằng thân cây ngô vào mùa thu, sau khi thu hoạch hạt. Bạn vẫn còn thời gian giúp thiết kế mê cung tuyệt vời nhất cho năm 2010.

Cánh đồng phủ đầy thân cây ngô, trừ một số chướng ngại như cây cối, công trình, nơi ngô không mọc được. Những thân cây rất cao tạo thành tường mê cung. Lối đi được tạo trên lưới ô vuông bằng cách giẫm đổ ngô trong các ô kích thước \(1\text{ m}\times1\text{ m}\). Một ô ở biên là lối vào, và một ô là tâm mê cung.

Jack tới mê cung ngô hằng năm và đã rất giỏi tìm đường nhanh nhất từ lối vào tới tâm. Bạn phải chọn những ô ngô cần giẫm đổ để số ô Jack buộc phải đi qua lớn nhất có thể. Trình chấm tự xác định lối vào (ô lối đi duy nhất trên biên) và tâm (ô mà Jack phải đi xa nhất để tới được).

Bản đồ cánh đồng hình chữ nhật được biểu diễn bằng văn bản. Ký tự # là ô ngô còn đứng; X là chướng ngại không thể giẫm đổ. Chỉ được thay một số # bằng dấu chấm . để tạo lối đi. Đúng một ô . phải nằm trên biên; mọi ô . còn lại nằm bên trong. Chỉ được đi giữa hai ô . có chung cạnh.

Độ dài \(P\) là số ô trên đường đi ngắn nhất từ lối vào tới ô có khoảng cách lớn nhất mà có thể đi tới, tính cả lối vào và ô cuối. Mục tiêu là làm \(P\) lớn nhất. Theo trình chấm chính thức, khoảng cách được tính trong phần có thể đi tới từ lối vào; chu trình không bị cấm và các ô không thể đi tới không làm tăng \(P\).

Dữ liệu vào

Đây là bài chỉ nộp kết quả. Tải fields.zip, gồm mười cánh đồng cố định field1.txt, …, field9.txt, fieldA.txt. Mỗi tệp chỉ chứa các hàng của bản đồ, không có dòng ghi kích thước. Không có dữ liệu ngẫu nhiên hay bộ kiểm tra ẩn ngoài mười cánh đồng này.

Dữ liệu ra

Nộp một tệp ZIP chứa tệp maze.txt. Tệp này gồm lần lượt kết quả cho field1.txt, …, field9.txt, fieldA.txt, viết liền nhau theo đúng thứ tự và không có dòng phân cách. Kích thước của mười phần lần lượt là 6, 100, 100, 100, 100, 11, 20, 20, 11, 200 dòng. templates.zip chứa sẵn một tệp maze.txt hợp lệ theo đúng định dạng này.

Trong mỗi phần, phải giữ nguyên số ký tự trên mỗi dòng và mọi vị trí X. Chỉ được thay # thành . hoặc giữ nguyên #; không thêm ký tự, khoảng trắng, hàng trống hoặc nội dung sau bản đồ. Đúng một ô biên phải là .. Nếu bất kỳ phần nào không hợp lệ, bài nộp nhận 0 điểm.

Ràng buộc

Các kích thước và tham số chấm được nêu đầy đủ trong bảng dưới. Chỉ có ba ký tự #, X, . trong kết quả; tệp đầu vào chỉ có #, X. Hai ô kề chéo không nối với nhau.

Phân nhóm

Mỗi cánh đồng là một nhóm độc lập. Với kết quả hợp lệ có độ dài \(P\), điểm gốc của nhóm có tham số \(T\) là:

Trong kỳ thi gốc, kiểm tra công khai cho 1 điểm mỗi nhóm nếu kết quả hợp lệ, bất kể độ dài; kiểm tra chính thức cho phần điểm còn lại. Tổng điểm gốc được làm tròn tới số nguyên gần nhất trong khoảng 0 đến 110. Công thức \(s\) ở trên đã bao gồm phần điểm cho tính hợp lệ, không cộng thêm 1 lần nữa.

Trên LQDOJ, cả mười cánh đồng được chấm trong cùng một lượt để phần thưởng của cánh đồng này vẫn có thể bù cho cánh đồng khác như cách cộng điểm gốc. Gọi \(S\) là tổng mười giá trị \(s(P,T)\). Điểm LQDOJ là \(\min(100,S)\), không làm tròn. Vì vậy bài vẫn dùng nguyên công thức gốc và phần thưởng lịch sử trên 100 được chặn ở 100.

Ví dụ

##X#######
###X######
####X##X##
##########
##XXXX####
##########

#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########

#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########

Chi tiết triển khai

Bài không có giao diện hàm, không nộp mã nguồn. Trong môi trường gốc, các tệp nằm trong /home/ioi2010-contestant/maze/. Trình chấm mẫu grader.c/.cpp/.pas đọc bản đồ qua grader.in.*, ghi OK N P khi đó là mê cung hợp lệ của nhóm N với độ dài P. Các tệp maze*.txt mẫu rất đơn giản có thể chép thành grader.in.* để thử. Môi trường IOI gốc nộp mười tệp riêng; LQDOJ ghép đúng mười nội dung đó vào một tệp maze.txt trong ZIP để toàn bộ điểm được tính chung.

Nguồn

IOI 2010, ngày 2, bài 3 — Maze. Đề chính thức, PDF tiếng Anh.