SP13118 PUCMM335 - The Rook and The Rookette

从前，有一辆名叫丹尼的高贵的车，它在一个普通的 8x8 国际象棋棋盘上生活。棋盘上的所有格子都和睦相处，而丹尼是一辆快乐的车，能够上下左右地在棋盘上自由移动，但从不越界。哦，他真是太享受这种移动了！他每天都忙于拜访所有的 64 个格子，并带去鲜花和礼物。所有的格子都很喜欢丹尼，尽管他们为他感到遗憾，因为他没有一个可以相伴的车后。 国王注意到了这些议论，于是做了一件了不起的事情。他为丹尼安排了一次与来自另一个棋盘的车后玛丽亚的约会。当玛丽亚走到一个格子上时，丹尼便迫不及待地跟了过去。然而，国王故意不让事情那么容易。他对丹尼说道：“丹尼，我们都非常爱你。我现在所做的这一切都是出于对你的爱。”丹尼感到困惑，问道：“尊敬的国王，您是什么意思？”突然，国王在棋盘上放置了 M 枚炸弹，“生活中，梦想需要通过努力去实现。我不能直接把玛丽亚交给你。你需要通过努力来赢得与她约会的权利。” “呃……”丹尼半信半疑地答道。“我也许会站在某个格子上。去追她吧！” 于是丹尼出发了。假设丹尼非常渴望见到玛丽亚，他会选择最短路径去找她。而国王希望能够延长丹尼的路径（或许是为了让他思考如何成长为一个真正的男子汉）。国王需要决定站在哪个空格子上，他有 N 个空格子可供选择。 请编写一个程序，输出如果丹尼和国王都采取最佳策略时，丹尼到达玛丽亚的路径长度。题目保证总会有一条可行的路径。

输入文件包含一个测试用例。前 8 行每行有 8 个字符，表示棋盘的初始状态，每行和每列分别从 0 到 7 编号。位置 (i, j) 的字符可以是以下之一： - `.` ：空格子 - `#` ：炸弹 - `?` ：公主 - `$` ：丹尼 随后的一行包含一个整数 $N$（$0 \le N \le 10$），表示国王可以选择的位置数。接下来的 $N$ 行，每行包含两个整数 $X_i, Y_i$（$0 \le X_i, Y_i \le 7$），表示一个空格子的位置。

输出一个整数，表示丹尼到达玛丽亚的最短路径长度，如果丹尼和国王都采取最佳策略。 ## 提示 - $0 \le N \le 10$ - $0 \le X_i, Y_i \le 7$ ## 示例 ### 输入 ``` $......? ######## ######## ######## ######## ######## ######## #######. 1 7 7 ``` ### 输出 ``` 7 ``` **本翻译由 AI 自动生成**