Gurin and Malon are a couple of penguins living in Binary Land, a marvelous country. They are trapped in a mystical maze, described as a grid with cells that are either free spaces or walls. Exactly one of the free spaces is designated as the love cell, having a nice heart inside a cage. Gurin and Malon are initially located at two free spaces inside the maze. The maze is surrounded by walls, so no penguin can move outside it because, as everyone knows, penguins cannot move through walls. Gurin (right) and Malon (left) trapped in the maze. North is upside and West is leftside. Original image taken from Binary Land, Hudson Soft Co., Ltd. Both penguins can move freely through the free spaces, until they meet at the love cell, where they can fall in love together. At any given time, a penguin can move from its current cell to an adjacent cell in one of four possible directions: north, south, east and west. However, Gurin and Malon were cursed by an evil witch! If a penguin goes north or south, then the other must automatically go in the same direction; and, if a penguin goes east or west, then the other must automatically go in the opposite direction. As it was mentioned before, no penguin can move through a wall and additionally, both penguins can be in the same cell at any given time. In detail, the curse works as follows: • If a penguin has a free cell to the north and it moves one step to the north, then the other penguin must move one step to the north (at the same time). However, if the other penguin had a wall to the north, it must stay in its current cell. • If a penguin has a free cell to the south and it moves one step to the south, then the other penguin must move one step to the south (at the same time). However, if the other penguin had a wall to the south, it must stay in its current cell.
2/3 • If a penguin has a free cell to the west and it moves one step to the west, then the other penguin must move one step to the east (at the same time). However, if the other penguin had a wall to the east, it must stay in its current cell. • If a penguin has a free cell to the east and it moves one step to the east, then the other penguin must move one step to the west (at the same time). However, if the other penguin had a wall to the west, it must stay in its current cell. Each cursed move of both penguins takes exactly one unit of time. Given a maze, the coordinates of the love cell, and the initial coordinates of Gurin and Malon, what is the minimum amount of time in which both penguins can fall in love together? Input The input consists of several test cases. The first line of a test case contains two blank-separated integers R and C (1 ≤ R ≤ 40, 1 ≤ C ≤ 40) indicating, respectively, the number of rows and columns of the maze (without the surrounding walls). The second line contains six blank-separated integers rL, cL, rG, cG, rM, and cM (1 ≤ rL,rG,rM ≤ R, and 1 ≤ cL,cG,cM ≤ C) indicating the coordinates (rL,cL) of the love cell, the initial coordinates (rG, cG) of Gurin, and the initial coordinates (rM , cM ) of Malon. Each of the next R lines contains C characters ‘.’ or ‘#’, where ‘.’ represents a free space and ‘#’ represents a wall. You may assume that the coordinates (rL, cL), (rG, cG) and (rM , cM ) correspond to free spaces, and that the given maze is surrounded by walls. Output For each test case, output a single line with the minimum amount of time in which both penguins can meet at the love cell or with the text ‘NO LOVE’ if it is impossible for them to meet at the love cell. Sample Input 10 15 1 8 10 9 10 7 ............... .###.###.###.## ##.#.#.###.#.#. .......#....... .#####.#.#####. .......#....... ##.#.#.#.#.#.## .......#....... .#############. .......#....... 33 123232 ... .#. ... 33 123232 ...
... 33
3/3 323232 ...
... Sample Output 31 4 NO LOVE 0