Camelot
Nhiều thế kỷ trước, vua Arthur và các Hiệp sĩ bàn tròn thường gặp gỡ mỗi năm vào ngày đầu năm mới để ăn mừng tình bằng hữu của họ. Trong ký ức của những sự kiện này, chúng ta xem xét một trò chơi dành cho một người, mà một trong những vị vua và một vài miếng hiệp sĩ được đặt ngẫu nhiên trên ô vuông riêng biệt.
Tấm bảng là một mảng 8x8 của hình vuông.
Hình 1. Bảng
Nhà vua có thể di chuyển đến bất kỳ vuông liền kề từ
đến
, như thể hiện trong hình 2, miễn là nó không rơi ra khỏi hội đồng quản trị.
Hình 2. Tất cả những bước đi có thể có của nhà vua
Một hiệp sĩ có thể nhảy từ
đến
, như thể hiện trong hình 3, miễn là nó không rơi ra khỏi bảng.
Hình 3. Tất cả những bước đi có thể có của một hiệp sĩ
Trong quá trình chơi, người chơi có thể đặt nhiều hơn một quân trong cùng một ô vuông. Các hình vuông của bảng được giả định đủ lớn để một quân không bao giờ là một trở ngại cho quân khác di chuyển tự do.
Mục tiêu của người chơi là di chuyển các quân để quy tụ tất cả trong cùng một hình vuông, trong số bước di chuyển nhỏ nhất có thể. Để đạt được điều này, người chơi phải di chuyển các quân theo quy định trên. Ngoài ra, bất cứ khi nào nhà vua và một hoặc nhiều hiệp sĩ được đặt trong cùng một hình vuông, người chơi có thể chọn để di chuyển vua và một trong những hiệp sĩ với nhau từ đó, như một hiệp sĩ duy nhất, cho đến thời điểm cuối cùng. Di chuyển các hiệp sĩ cùng với vua được tính như một bước duy nhất.
Yêu cầu:
Viết một chương trình để tính toán số bước đi tối thiểu mà người chơi phải thực hiện để tạo ra sự quy tụ.
Dữ liệu vào
Các CAMELOT.INP tập tin có chứa các cấu hình của bảng đầu, mã hóa như là một chuỗi ký tự. Các chuỗi có chứa một chuỗi lên đến 64 vị trí của bảng riêng biệt, gồm đầu tiên là vị trí của vị vua và những vị trí còn lại là của các hiệp sĩ. Mỗi vị trí là một cặp chữ số. Các chữ cho biết hoành độ, các chữ số cho biết tung độ.
Nhập liệu mẫu:
D4A3A8H1H8
Nhà vua là vị trí ở D4. Có bốn hiệp sĩ, vị trí ở A3, A8, H1, và H8.
Dữ liệu ra
Các tập tin CAMELOT.OUT có một dòng duy nhất với một số nguyên cho biết số bước di chuyển tối thiểu người chơi phải thực hiện để tạo ra sự quy tụ.
Đầu ra mẫu:
10
Những hạn chế
0 ≤ số hiệp sĩ ≤ 63
Nhiều thế kỷ trước, vua Arthur và các Hiệp sĩ bàn tròn thường gặp gỡ mỗi năm vào ngày đầu năm mới để ăn mừng tình bằng hữu của họ. Trong ký ức của những sự kiện này, chúng ta xem xét một trò chơi dành cho một người, mà một trong những vị vua và một vài miếng hiệp sĩ được đặt ngẫu nhiên trên ô vuông riêng biệt.
Tấm bảng là một mảng 8x8 của hình vuông.
Hình 1. Bảng
Nhà vua có thể di chuyển đến bất kỳ vuông liền kề từ
đến
, như thể hiện trong hình 2, miễn là nó không rơi ra khỏi hội đồng quản trị.
Hình 2. Tất cả những bước đi có thể có của nhà vua
Một hiệp sĩ có thể nhảy từ
đến
, như thể hiện trong hình 3, miễn là nó không rơi ra khỏi bảng.
Hình 3. Tất cả những bước đi có thể có của một hiệp sĩ
Trong quá trình chơi, người chơi có thể đặt nhiều hơn một quân trong cùng một ô vuông. Các hình vuông của bảng được giả định đủ lớn để một quân không bao giờ là một trở ngại cho quân khác di chuyển tự do.
Mục tiêu của người chơi là di chuyển các quân để quy tụ tất cả trong cùng một hình vuông, trong số bước di chuyển nhỏ nhất có thể. Để đạt được điều này, người chơi phải di chuyển các quân theo quy định trên. Ngoài ra, bất cứ khi nào nhà vua và một hoặc nhiều hiệp sĩ được đặt trong cùng một hình vuông, người chơi có thể chọn để di chuyển vua và một trong những hiệp sĩ với nhau từ đó, như một hiệp sĩ duy nhất, cho đến thời điểm cuối cùng. Di chuyển các hiệp sĩ cùng với vua được tính như một bước duy nhất.
Yêu cầu:
Viết một chương trình để tính toán số bước đi tối thiểu mà người chơi phải thực hiện để tạo ra sự quy tụ.
Dữ liệu vào
Các CAMELOT.INP tập tin có chứa các cấu hình của bảng đầu, mã hóa như là một chuỗi ký tự. Các chuỗi có chứa một chuỗi lên đến 64 vị trí của bảng riêng biệt, gồm đầu tiên là vị trí của vị vua và những vị trí còn lại là của các hiệp sĩ. Mỗi vị trí là một cặp chữ số. Các chữ cho biết hoành độ, các chữ số cho biết tung độ.
Nhập liệu mẫu:
D4A3A8H1H8
Nhà vua là vị trí ở D4. Có bốn hiệp sĩ, vị trí ở A3, A8, H1, và H8.
Dữ liệu ra
Các tập tin CAMELOT.OUT có một dòng duy nhất với một số nguyên cho biết số bước di chuyển tối thiểu người chơi phải thực hiện để tạo ra sự quy tụ.
Đầu ra mẫu:
10
Những hạn chế
0 ≤ số hiệp sĩ ≤ 63