trang chủ / đề bài / icpcwf05_h

Trò chơi Vạn Lý Trường Thành

Đề bài

Mô tả

Hua và Shen đã nghĩ ra một trò chơi xếp hình một người chơi đơn giản mà họ gọi là "Trò chơi Vạn Lý Trường Thành". Trò chơi được chơi với n viên đá trên một bảng ô vuông n×n. Các viên đá được đặt ngẫu nhiên vào các ô của bảng, mỗi ô có nhiều nhất một viên đá. Trong một bước đi, một viên đá bất kỳ có thể di chuyển sang một ô trống kề nó theo chiều ngang hoặc chiều dọc (cách đúng một đơn vị). Mục tiêu của trò chơi là tạo ra một "bức tường", tức là xếp cả n viên đá thẳng hàng theo chiều ngang, chiều dọc hoặc theo đường chéo, với số bước đi ít nhất.

Hình dưới minh hoạ trường hợp n=5: bảng ban đầu (các ô tô màu là các viên đá, hàng đánh số 1..5 từ trên xuống, cột đánh số 1..5 từ trái sang). Với sáu bước đi, ta có thể xếp cả năm viên đá theo đường chéo: viên đá ở ô (1,2) đi sang phải 3 bước tới ô (1,5), viên ở ô (3,4) đi sang trái 1 bước tới ô (3,3), viên ở ô (5,3) đi lên 1 bước rồi sang trái 1 bước tới ô (4,2). Không có cách nào dùng ít hơn sáu bước để xếp được một hàng năm viên đá. (Tuy nhiên vẫn có những cách khác cũng dùng sáu bước, chẳng hạn xếp cả năm viên đá vào cột thứ ba.)

grid
.....
.....
.....
.....
.....
step Bảng ban đầu
highlight blue 1,2 2,4 3,4 5,1 5,3
step Một cách dùng 6 bước: xếp theo đường chéo
clear
highlight gray 1,2 3,4 5,3
path orange 1,2 1,3 1,4 1,5
path orange 3,4 3,3
path orange 5,3 4,3 4,2
highlight blue 1,5 2,4 3,3 4,2 5,1

Vấn đề duy nhất là Hua và Shen không biết số bước đi ít nhất cho một bảng ban đầu bất kỳ là bao nhiêu. Họ muốn bạn viết chương trình nhận vào một cách đặt ban đầu bất kỳ và tính số bước đi ít nhất cần để tạo thành một bức tường.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên n (1≤n≤15). Dòng tiếp theo chứa số hiệu hàng và số hiệu cột của viên đá thứ nhất, tiếp theo là số hiệu hàng và số hiệu cột của viên đá thứ hai, và cứ thế tiếp tục (2n số nguyên). Hàng và cột được đánh số từ 1 đến n như trong hình trên. Các viên đá nằm ở các ô đôi một khác nhau.

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

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test (1,2,…) và số bước đi ít nhất cần để xếp n viên đá thành một bức tường thẳng hàng, theo đúng định dạng của ví dụ: Board k: m moves required. (luôn viết moves, kể cả khi m≤1).

Ràng buộc

  • 1≤n≤15.
  • 1≤ số hiệu hàng, số hiệu cột ≤n; không có hai viên đá ở cùng một ô.
  • Mỗi file có không quá 10 bộ test.

Ví dụ

Input Output Giải thích
5
1 2 2 4 3 4 5 1 5 3
2
1 1 1 2
3
3 1 1 2 2 2
0
Board 1: 6 moves required.
Board 2: 0 moves required.
Board 3: 1 moves required.
Bộ 1 là bảng trong hình. Bộ 2: hai viên đá đã nằm trên hàng 1. Bộ 3: chuyển viên đá ở ô (3,1) lên ô (2,1) để được hàng 2.
1
1 1
3
1 3 2 2 3 1
4
1 4 2 3 3 2 4 2
0
Board 1: 0 moves required.
Board 2: 0 moves required.
Board 3: 1 moves required.
Bộ 1: một viên đá đã là một bức tường. Bộ 2: ba viên đá đã nằm trên đường chéo phụ. Bộ 3: chuyển viên đá ở ô (4,2) sang ô (4,1) để được đường chéo phụ (1,4),(2,3),(3,2),(4,1); mọi hàng hay cột đều cần ít nhất 3 bước.

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