Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NTKING - King vs Knights

Hàng trăm năm về trước, vua Arthur và các kị sĩ của Hội Bàn Tròn thường gặp gỡ vào ngày đầu năm mới để kỉ niệm mối giao hảo của họ. Để tưởng nhớ những sự kiện này, chúng ta lập ra một trò chơi với bàn cờ và một người chơi, trên đó một quân vua và nhiều quân mã được đặt trên các ô, không có quân mã nào nằm trên cùng một ô.

Bàn cờ ví dụ dưới đây là một bàn cờ chuẩn 8x8:

http://ace.delos.com/usaco/probs/camelot-1.gif

Quân vua có thể di chuyển đến bất kì ô liền kề nào từ đến miễn là nó không rơi ra khỏi bàn:

http://ace.delos.com/usaco/probs/camelot-2.gif

Quân mã có thể nhảy từ đến , miễn là nó không rơi ra khỏi bàn:

http://ace.delos.com/usaco/probs/camelot-3.gif

Trong quá trình chơi, người chơi có thể đặt nhiều hơn một quân cờ trên cùng một ô. Các ô trên bàn cờ được xem như đủ rộng để không có quân cờ nào trở thành chướng ngại vật khiến quân cờ khác không thể di chuyển dễ dàng.

Mục đích của người chơi là di chuyển các quân cờ về cùng một ô - với số bước đi ít nhất. Để đạt được điều này, người chơi phải di chuyển các quân cờ như chỉ dẫn ở trên. Thêm nữa, khi con vua và một hoặc nhiều con mã được đặt trong cùng một ô, người chơi có thể chọn để di chuyển vua với một con mã cùng nhau từ ô đó trở về sau, như là một con mã, cho đến điểm tập hợp. Di chuyển con mã cùng con vua sẽ được tính là một bước đi.

Viết một chương trình tính số bước ít nhất mà người chơi cần để tập hợp các quân cờ vào cùng một ô. Dĩ nhiên là các quân cờ có thể tập hợp ở bất kì ô nào.

Input

Dòng 1: Hai số nguyên cách nhau bởi khoảng trắng: R,C, số dòng và cột của bàn cờ. Sẽ không có nhiều hơn 26 cột và nhiều hơn 40 dòng.
Dòng 2..cuối: Tập tin input chứa một chuỗi các cặp chữ cái/chữ số cách nhau bởi khoảng trắng, 1 hoặc nhiều hơn 1 dòng. Cặp đầu tiên mô tả vị trí trên bàn cờ của con vua; các cặp tiếp theo mô tả vị trí của các con mã. Có thể không có con mã nào hoặc các con mã phủ kín bàn cờ. Các dòng được đánh số từ 1; các cột được mô tả bằng chữ cái in hoa bắt đầu bằng A

Output

Một dòng ghi số bước đi cần thiết để tập hợp các quân cờ.

Example

Input:
8 8
D 4
A 3 A 8
H 1 H 8
Output:
10

Giải thích:

Các quân cờ tập hợp tại B5.
Con mã 1: A3 - B5 (1 bước)
Con mã 2: A8 - C7 - B5 (2 bước)
Con mã 3: H1 - G3 - F5 - D4 (đón con vua) - B5 (4 bước)
Con mã 4: H8 - F7 - D6 - B5 (3 bước)
1 + 2 + 4 + 3 = 10 bước.


Được gửi lên bởi:senga
Ngày:2010-01-06
Thời gian chạy:0.200s-0.300s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:IOI' 98

hide comments
2010-12-16 13:38:07 Nguyên
Input không chuẩn như USACO, nên cẩn thận trong lúc đọc =.=
2010-05-05 15:41:40 Tran Dang Tuan Anh
PS xem hộ minh bị WA hay TLE cái, đã AC trên USACO rồi mà :(
2010-02-22 06:22:24 Hy Trường Sơn
ps ơi, mình đọc input bằng eof thì được 63 điểm, đọc input bằng seek eof thì được 68 điểm, giải thích hộ với +_+
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.