Kirill is a great gardener. He loves his garden and takes good care of
the plants. The jewel of the garden is a huge green maze. Its walls are
hundreds of meters long and consist of intertwined branches of wild
bushes. One evening Kirill was trimming the grape leaves when he
suddenly realized a horrible fact: he got so consumed by the gardening
routine that he haven’t been doing any of his house chores! In fact, the
kitchen sink is full of dirty dishes and the potato is lying unpeeled. To
make things worse, Kirill’s parents will arrive soon. They will surely
punish the boy for his bad behavior… He must detain them and finish the
chores! Luckily for Kirill, the only way to the house is through the maze.
But his parents walk through the maze every day and know the shortest path
good. So there’s only one thing Kirill can do: he
should alter the maze making the shortest path in it as long as
possible. The boy is running out of time so he can plant only one new bush
to block some way. But where should he plant it?
The maze can be represented as a grid of n rows and m columns. Each
bush takes up a single 1×1 square. Some cells are initially
occupied by bushes and some cells are empty. One can move from any cell to
empty side-adjacent cells only. Besides, the maze has two marked cells:
the parking space where Kirill’s parents will be situated and the house
they will want to get to. Kirill’s task is to choose exactly one empty
cell (naturally, this cell mustn’t be the parking space or the house) and
to plant a bush in it so that the length of the shortest path from the
parking space to the house would be maximum possible.
The first line contains integers n and m that are the number of rows
and columns in the maze, correspondingly (2 ≤ n, m ≤ 1000;
n · m ≤ 105). The second line contains the coordinates of the
parking space (row number and column number). The rows are numbered from
the top starting from 1 and the columns are numbered from the left
starting from 1. The third line contains the coordinates of the house in
the same format. The next n lines contain m characters each and
describe the maze. Each line consists of characters “.” (for an empty
cell) and “#” (for a bush). It is guaranteed that the coordinates of
the parking space and the house do not coincide, both these cells are
empty, and a path from the parking space to the house exists. It is also guaranteed that the maze has at least one empty cell
besides these two cells.
Output the coordinates of the cell (row number and column number) where
Kirill should plant a bush in order to maximize the length of the shortest
path from the parking space to the house.
If it is possible to plant a bush so that there will be no path
from the parking space to the house, Kirill should do it because in this
case the parents will have to dig a tunnel to get out of the maze and
Kirill will surely have enough time. If there are multiple optimal
choices, you may output any of them.
Problem Author: Ilya Kuchumov. (Prepared by Oleg Merkurev)
Problem Source: Ural Regional School Programming Contest 2013