CAMELOT
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Vua Arthur và các hiệp sĩ bàn tròn thường gặp nhau vào đầu năm mới để ăn mừng tình bạn của họ. Để tưởng nhớ sự kiện này, chúng ta xem xét một trò chơi, trong đó có một quân vua và một vài quân mã được đặt ngẫu nhiên trên các ô riêng biệt. Bàn cờ có kích thước \(n × n\), trên bàn cờ có một số ô cấm những ô còn lại là những ô tự do – ô có thể di chuyển vào được. Các ô đặt quân mã và quân vua đang đứng ở các ô tự do.
Tại mỗi bước tất cả các quân đều phải di chuyển theo quy tắc và không được đi vào ô cấm, hãy tìm cách di chuyển để chúng gặp nhau nhanh nhất.
Input
- Dòng đầu là số \(n\);
- \(n\) dòng tiếp theo, mỗi dòng 1 xâu \(n\) ký tự, gồm các ký tự
.thể hiện ô trống,#thể hiện ô cấm không được phép đi vào,Tthể hiện vị trí vua đang đứng,Mthể hiện vị trí quân mã đang đứng.
Output
- Gồm một số là số bước ít nhất để các quân gặp nhau, nếu không thể gặp được nhau ghi \(-1\).
Scoring
- Subtask \(1\): \(n ≤ 20\) và chỉ có một quân mã;
- Subtask \(2\): \(n ≤ 100\) và chỉ có một quân mã;
- Subtask \(3\): \(n ≤ 100\).
Example
Test 1
Input
5
M....
.....
.#...
.#..#
...#TOutput
2
Bình luận
em xin lỗi mọi người ạ vì em treo máy nên bị bạn trêu ạ 🙁
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.