| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT133H - Trò chơi xếp hình |
Hãy tưởng tượng lại trò chơi xếp hình với các miếng ghép trượt mà các bạn hay chơi hồi nhỏ!
Một miếng gỗ hình chữ nhật nền có chiều dài H và chiều rộng W, và trong nó chứa các miếng ghép có thể di chuyển xen kẽ với nhau.
Có 3 loại miếng ghép, 1 miếng 2x2 là vua, một số miếng là các con tốt, một số miếng là các vật cản cố định, và có đúng 2 ô trống.
1 miếng ghép chỉ có thể di chuyển theo 1 hướng nếu như ô phía trước (theo hướng ấy) là một ô trống, khi đó, ta sẽ đẩy miếng ghép đi, và tạo ra một ô trống tại vị trí cũ.
Nhiệm vụ của bạn là di chuyển miếng ghép của vua lên góc trên bên trái. Hãy tính số bước thực hiện ít nhất.
Hình vẽ minh họa cho test 4.
Input
Gồm nhiều bộ test.
Mỗi bộ test bắt đầu bằng 2 số H và W (chiều cao và chiều rộng của miếng hình nền, 3 ≤ H, W ≤ 50).
H dòng tiếp theo, mỗi dòng chứa W kí tự, đại diện cho các miếng ghép.
'X', 'o', '*', '.' lần lượt là các ô chứa vua, tốt, ô vật cản và ô trống.
Input kết thúc bởi 2 số 0.
Output
Với mỗi test, in ra số bước di chuyển tối thiểu để di chuyển vua tới góc trên bên trái. Nếu không thực hiện được, in ra -1.
Example
Input:
3 3 oo. oXX .XX 3 3 XXo XX. o.o 3 5 .o*XX oooXX oooo. 7 12 oooooooooooo ooooo*****oo oooooo****oo o**ooo***ooo o***ooooo..o o**ooooooXXo ooooo****XXo 5 30 oooooooooooooooooooooooooooooo oooooooooooooooooooooooooooooo o***************************oo XX.ooooooooooooooooooooooooooo XX.ooooooooooooooooooooooooooo 0 0Output:
11 0 -1 382 6807
| Được gửi lên bởi: | adm |
| Ngày: | 2013-02-16 |
| Thời gian chạy: | 3s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
