Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Traveling Queen Problem
Description Black has been defeated and the white army has won, but unfortunately the white king has been killed in the fight, and so the white queen is looking for a new mate. She is unsure whom of the knights to marry and has decided to visit them all. Afterwards she plans to see the bishop to arrange for the marriage. Given a chessboard with the current situation, find the shortest number of moves such that the queen visits every knight and, finally, visits the bishop. The queen visits by standing on one of the (at most) eight neighbouring squares and she does not necessarily have to move between two visits. For each move the queen can go an arbitrary number of squares in one of the eight directions (horizontal, vertical or diagonal). No move may pass through or stop at a non-empty square. Input The first line contains the number of scenarios. Each scenario consists of a chessboard description. The rows There is one character Output The output for every scenario begins with a line containing “ Then print the Sample Input 2 .......Q ...P.P.. ...PNP.. ..NP.P.. ........ ........ ..B..... ........ B.P..... ..P..... PPP..N.. ........ ........ .N...Q.. ........ ........ Sample Output Scenario #1: h8h2e5d4b2 Scenario #2: impossible Source TUD Programming Contest 2006, Darmstadt, Germany |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator