问题 1412. -- XY之说走就走的旅行

1412: XY之说走就走的旅行

时间限制:1000 ms 内存限制:128 MB
提交:984 解决:144
[ 提交][ 状态][ 讨论版]

题目描述

X和Y是好基友,他们决定进行一次说走就走的旅行,因此俩人约好在车站会合。

城市中有多个车站,为了节省时间,他们约好的车站应该离双方的家都比较近。

即若X与车站i距离为dXi,Y与车站i距离为dYi,则该车站为max(dXi,dYi)最小的车站。(只有‘#’的位置无法通过)


输入

多组数据,请处理到文件尾。

对于每组数据:

第一行含有两个正整数n,m

接下来是一个n行m列的矩阵,表示城市地图,矩阵中任意元素只和上下左右元素(如果存在且可达)相邻,相邻元素之间距离为1。

其中” . ”代表可走的街道,” # ”代表不可走的街道,” P ”表示车站,” X ”代表X的家,” Y ”代表Y的家。


输出

对于每组数据输出一行,含有两个整数x,y,以空格分隔,代表约定好的车站所在的行号和列号(1<=x<=n,1<=y<=m)。

若存在多个满足条件的解,则答案应为行号最小的;若还存在多个解,则答案应应为列号最小的。

保证解一定存在。

样例输入

3 3 X.P P#. ..Y 2 2 XP PY

样例输出

1 3 1 2

提示

1<=n,m<=200

关于多组数据的读入方式,在B题中给出了例子

本题此前数据较弱,赛后略有加强

来源

[ 提交][ 状态][ 讨论版]
Baidu
map