X和Y是好基友,他们决定进行一次说走就走的旅行,因此俩人约好在车站会合。
城市中有多个车站,为了节省时间,他们约好的车站应该离双方的家都比较近。
即若X与车站i距离为dXi,Y与车站i距离为dYi,则该车站为max(dXi,dYi)最小的车站。(只有‘#’的位置无法通过)
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题中给出了例子
本题此前数据较弱,赛后略有加强