trang chủ / đề bài / icpcwf07_f

Trò chơi bi

Đề bài

Mô tả

Trò chơi bi được chơi với M viên bi trên một bàn hình vuông. Bàn được chia thành N×N ô vuông đơn vị, trong đó có M ô chứa lỗ. Các viên bi và các lỗ được đánh số từ 1 đến M. Mục tiêu của trò chơi là lăn mỗi viên bi vào lỗ có cùng số với nó.

Bàn chơi có thể có các bức tường. Mỗi bức tường dài một đơn vị và nằm giữa hai ô kề nhau. Hai ô được coi là kề nhau khi và chỉ khi chúng có chung một cạnh.

Khi bắt đầu trò chơi, tất cả các viên bi được đặt trên bàn, mỗi viên ở một ô khác nhau. Một "nước đi" là nhấc nhẹ một cạnh của bàn chơi lên. Khi đó mọi viên bi trên bàn lăn xuống về phía cạnh đối diện, mỗi viên lăn cho tới khi gặp một bức tường, hoặc rơi vào một lỗ còn trống, hoặc khi ô tiếp theo đã có một viên bi khác chiếm. Các viên bi lăn theo các quy tắc sau:

  • Bi không thể nhảy qua tường, qua viên bi khác hay qua lỗ còn trống.
  • Bi không thể rời khỏi bàn (mép bàn là tường).
  • Mỗi ô chứa nhiều nhất một viên bi tại mọi thời điểm.
  • Khi một viên bi đi vào ô có lỗ (còn trống), viên bi rơi vào lỗ đó. Khi đó lỗ đã được lấp, và các viên bi khác có thể lăn qua lỗ này về sau. Viên bi đã nằm trong lỗ không bao giờ rời khỏi lỗ được nữa.

Trò chơi kết thúc khi mỗi viên bi đã rơi vào lỗ có số tương ứng.

Hình dưới minh hoạ một lời giải cho ván chơi trên bàn 4×4 với ba viên bi (màu xanh đậm), ba lỗ và một bức tường. Lời giải gồm năm nước: nhấc cạnh phía đông, nhấc cạnh phía bắc, nhấc cạnh phía nam, nhấc cạnh phía tây, nhấc cạnh phía bắc (hàng đánh số từ trên xuống, phía bắc ở trên, phía đông ở bên phải).

Hãy xác định số nước đi ít nhất để đưa tất cả các viên bi vào đúng lỗ của chúng, nếu có cách làm được.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên của mỗi bộ test chứa ba số nguyên: kích thước N của bàn, số viên bi M và số bức tường W. Mỗi dòng trong 2M dòng tiếp theo chứa hai số nguyên: số đầu là chỉ số hàng, số thứ hai là chỉ số cột. M dòng đầu tiên trong số đó là vị trí các viên bi: viên bi số 1 ở dòng đầu, viên bi số 2 ở dòng thứ hai, và cứ thế. M dòng sau là vị trí các lỗ: lỗ số 1 trước, rồi lỗ số 2, và cứ thế. Cuối cùng, W dòng tiếp theo cho vị trí các bức tường. Mỗi dòng gồm bốn số nguyên: cặp số đầu là hàng và cột của ô ở một phía bức tường, cặp số sau là hàng và cột của ô ở phía bên kia. Hàng và cột được đánh số từ 0 đến N−1.

Dữ liệu vào kết thúc bằng một dòng chứa ba 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ố nước đi ít nhất để thắng, theo dạng Case k: X moves (luôn dùng chữ moves, kể cả khi X=1). Nếu không thể thắng, in Case k: impossible. In một dòng trống sau kết quả của mỗi bộ test. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 2≤N≤4, M≥1, W≥0.
  • M viên bi và M lỗ nằm ở 2M ô đôi một khác nhau (không viên bi nào nằm sẵn trên một lỗ).
  • Mỗi bức tường nằm giữa hai ô kề nhau trên bàn, không có hai bức tường trùng nhau.
  • Dữ liệu vào có không quá 5 bộ test.

Ví dụ

Input Output Giải thích
4 3 1
0 1
1 0
1 2
2 3
2 1
3 2
1 1 1 2
3 2 2
0 0
0 1
0 2
2 0
2 0 1 0
2 0 2 1
0 0 0
Case 1: 5 moves

Case 2: impossible

Bộ 1 là ván trong hình. Bộ 2: lỗ số 2 ở ô (2,0) bị tường chắn cả phía bắc lẫn phía đông, không viên bi nào lăn vào được.
2 1 0
0 0
0 1
4 2 0
1 1
1 0
1 2
1 3
3 2 1
0 0
0 1
0 2
2 2
0 1 1 1
0 0 0
Case 1: 1 moves

Case 2: 1 moves

Case 3: impossible

Bộ 2: nhấc cạnh phía tây, viên bi 1 ở phía trước rơi vào lỗ 1, viên bi 2 lăn qua lỗ vừa được lấp và rơi vào lỗ 2 ngay trong cùng nước đi. Bộ 3: mọi cách đi đều làm một viên bi rơi vào lỗ sai số (khi đó không thể thắng) hoặc không đưa được viên bi nào vào lỗ của nó.

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