trang chủ / đề bài / icpcwf10_i

Robot trên băng

Đề bài

Mô tả

Lấy cảm hứng từ những tác phẩm điêu khắc băng ở Cáp Nhĩ Tân, các thành viên đội tuyển lập trình của Đại học Robot và Tự động hóa Bắc Cực quyết định tổ chức lễ hội băng của riêng mình khi trở về sau kỳ thi. Họ dự định khai thác các khối băng từ một hồ nước gần đó khi hồ đóng băng vào mùa đông. Để tiện theo dõi độ dày của lớp băng, họ chia mặt hồ thành một lưới hình chữ nhật và cho một robot nhẹ đi từ ô này sang ô khác để đo độ dày băng tại mỗi ô.

Ba vị trí trong lưới được chọn làm các điểm "báo cáo", và robot phải gửi báo cáo tiến độ qua sóng vô tuyến từ các điểm này khi nó đi được một phần tư, một nửa và ba phần tư hành trình kiểm tra. Để tránh làm mòn mặt băng không cần thiết, robot phải bắt đầu hành trình từ góc dưới bên trái, có tọa độ (hàng, cột) là (0,0), đi qua mọi ô còn lại của lưới đúng một lần và kết thúc hành trình tại hàng 0, cột 1. Ngoài ra, nếu có nhiều hành trình robot có thể đi thì mỗi ngày sẽ dùng một hành trình khác nhau. Mỗi bước thời gian, robot chỉ có thể di chuyển sang một ô kề theo một trong bốn hướng: bắc, nam, đông, tây.

Bạn cần viết chương trình xác định có bao nhiêu hành trình khác nhau với kích thước lưới và dãy ba điểm báo cáo cho trước. Ví dụ, giả sử mặt hồ được chia thành lưới 3×6 và các điểm báo cáo, theo thứ tự đi qua, là (2,1), (2,4) và (0,4). Khi đó robot phải bắt đầu tại (0,0) và kết thúc tại (0,1) sau khi đi qua cả 18 ô. Robot phải có mặt tại ô (2,1) ở bước 4 (=⌊18/4⌋), tại ô (2,4) ở bước 9 (=⌊18/2⌋) và tại ô (0,4) ở bước 13 (=⌊3×18/4⌋). Có đúng hai cách làm điều này, như hình dưới (hàng 0 ở dưới cùng, các ô báo cáo được tô màu; ô (0,0) là ô thứ 1 của hành trình, ô (0,1) là ô thứ 18). Lưu ý rằng khi số ô của lưới không chia hết cho 4, phép chia lấy phần nguyên được dùng để tính ba thời điểm báo cáo.

Hành trình thứ nhất:

grid
......
......
......
path orange 3,1 2,1 1,1 1,2 2,2 2,3 1,3 1,4 1,5 1,6 2,6 3,6 3,5 2,5 2,4 3,4 3,3 3,2
highlight gray 1,2 1,5 3,5

Hành trình thứ hai:

grid
......
......
......
path orange 3,1 2,1 1,1 1,2 1,3 1,4 2,4 2,5 1,5 1,6 2,6 3,6 3,5 3,4 3,3 2,3 2,2 3,2
highlight gray 1,2 1,5 3,5

Lưu ý rằng một số cấu hình có thể không có hành trình hợp lệ nào. Ví dụ, với lưới 4×3 và dãy điểm báo cáo (2,0), (3,2), (0,2), không có hành trình nào bắt đầu tại (0,0) và kết thúc tại (0,1).

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên m và n là số hàng và số cột của lưới. Dòng tiếp theo chứa sáu số nguyên r1,c1,r2,c2,r3,c3.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ 1) và số hành trình bắt đầu tại hàng 0 cột 0, kết thúc tại hàng 0 cột 1, đi qua mỗi ô đúng một lần và có mặt tại hàng ri cột ci ở bước ⌊i×m×n/4⌋ với i=1,2,3 (ô xuất phát là bước 1, ô kết thúc là bước m×n). Làm theo đúng định dạng của ví dụ.

Ràng buộc

  • 2≤m,n≤8.
  • 0≤ri<m và 0≤ci<n với i=1,2,3.

Ví dụ

Input Output Giải thích
3 6
2 1 2 4 0 4
4 3
2 0 3 2 0 2
0 0
Case 1: 2
Case 2: 0
Ví dụ của đề gốc: hai bộ test được mô tả ở trên.
2 3
0 0 1 1 1 2
4 4
3 0 2 3 1 2
3 5
1 1 2 2 0 4
0 0
Case 1: 1
Case 2: 2
Case 3: 0
Bộ test 1: ⌊6/4⌋=1 nên điểm báo cáo đầu tiên phải là chính ô xuất phát; hành trình duy nhất là (0,0),(1,0),(1,1),(1,2),(0,2),(0,1). Bộ test 3: lưới có 15 ô, không có hành trình nào kết thúc tại (0,1).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0