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 viên đá trên một bảng ô vuông . 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ả 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 : bảng ban đầu (các ô tô màu là các viên đá, hàng đánh số từ trên xuống, cột đánh số 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 đá ở ô đi sang phải bước tới ô , viên ở ô đi sang trái bước tới ô , viên ở ô đi lên bước rồi sang trái bước tới ô . 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 (). 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 ( số nguyên). Hàng và cột được đánh số từ đế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ố .
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test () và số bước đi ít nhất cần để xếp 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 ).
Ràng buộc
- .
- số hiệu hàng, số hiệu cột ; không có hai viên đá ở cùng một ô.
- Mỗi file có không quá 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 . Bộ 3: chuyển viên đá ở ô lên ô để được hàng . |
| 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 đá ở ô sang ô để được đường chéo phụ ; mọi hàng hay cột đều cần ít nhất bước. |
https://oj.chuyentin.pro/problem/icpcwf05_h
Bình luận