trang chủ / đề bài / icpcwf18_j

Hành trình quân mã không tự cắt

Đề bài

Mô tả

Một câu đố nổi tiếng là cho quân mã "đi tuần" qua mọi ô của bàn cờ 8×8. Quân mã là quân cờ chỉ có thể di chuyển bằng cách nhảy một ô theo một hướng và hai ô theo hướng vuông góc với hướng đó. Quân mã phải đi qua mọi ô của bàn cờ, không ô nào lặp lại, rồi quay về ô xuất phát. Có rất nhiều cách làm điều này, và bàn cờ đủ nhỏ để một người có thể tự giải được.

Tuy nhiên, bạn có máy tính và biết lập trình! Vì vậy, chúng tôi đưa ra một phiên bản khó hơn của bài toán trên bàn cờ hình chữ nhật m×n với một ràng buộc bổ sung: quân mã không bao giờ được cắt ngang đường đi của chính nó. Hãy hình dung đường đi của quân mã gồm các đoạn thẳng nối tâm của các ô mà nó nhảy giữa chúng; các đoạn thẳng này phải tạo thành một đa giác đơn, tức là không có hai đoạn nào cắt nhau hoặc chạm nhau, ngoại trừ hai đoạn liên tiếp chạm nhau tại đầu mút chung. Ràng buộc này khiến việc đi qua mọi ô là không thể, vì vậy bạn cần làm cho số ô mà quân mã đi qua là lớn nhất. Ta vẫn giữ ràng buộc quân mã phải quay về ô xuất phát.

Hình dưới đây là một lời giải tối ưu cho ví dụ thứ nhất, bàn cờ 6×6.

Hình: một hành trình tối ưu đi qua 12 ô trên bàn cờ 6×6.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên m và n, kích thước của bàn cờ hình chữ nhật.

Dữ liệu ra

In ra số ô lớn nhất mà quân mã có thể đi qua trong một hành trình khép kín không tự cắt trên bàn cờ m×n. Nếu không tồn tại hành trình nào như vậy, in ra 0.

Ràng buộc

  • 1≤m≤8.
  • 1≤n≤1015.

Ví dụ

Input Output Giải thích
6 6 12 Hành trình ở hình minh họa đi qua 12 ô; không có hành trình không tự cắt nào dài hơn.
8 3 6 Bàn cờ 8 hàng, 3 cột: hành trình tốt nhất đi qua 6 ô.
7 20 80 Bàn cờ 7×20: hành trình tốt nhất đi qua 80 ô.
2 6 0 Với 2 hàng, mỗi ô chỉ nhảy được tới các ô cách 2 cột ở hàng kia, nên các nước đi nối các ô thành những dây không phân nhánh, không có chu trình. Quân mã không thể quay về ô xuất phát, nên không có hành trình nào.

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