Problem Description

Takahashi loves mazes. Now, he is trying to solve a maze on a two-dimensional board where he can move up, down, left, or right. The board is given in the following format:

• First, the size of the board and the coordinates of the start and goal points are given.
• Next, the board is provided with information about each cell being either a passable empty cell (.) or an impassable wall cell (#). The board is surrounded by wall cells. The start and goal points are always empty cells, and it is guaranteed that you can reach the goal from the start by following empty cells. Specifically, refer to the input/output examples for clarification.

Now, he wants to find the minimum number of moves required to solve the maze. While researching how to do this, he learned that the "breadth-first search" method is efficient. Breadth-first search is a technique where:

• The cells closest to the start (with the fewest moves required to reach) are determined first. The number of moves to reach each cell is confirmed as follows. For illustration, we will use the maze in Figure 1.

Figure 1. Board used for explanation

• Initially, the start cell is confirmed to be reachable in 0 moves (obviously), so its shortest path is set to 0 (Figure 2).

Figure 2. Cells reachable in 0 moves are confirmed (initial)

• Next, the four neighboring cells of the start cell are confirmed to be reachable in 1 move (Figure 3).

Figure 3. Cells reachable in 1 move are confirmed

• Then, for each cell confirmed in 1 move, look at their four neighbors. If any of these are unconfirmed empty cells, confirm them as reachable in 2 moves (Figure 4).

Figure 4. Cells reachable in 2 moves are confirmed

• Next, for each cell confirmed in 2 moves, look at their four neighbors. If any of these are unconfirmed empty cells, confirm them as reachable in 3 moves (Figure 5).

Figure 5. Cells reachable in 3 moves are confirmed

• Then, for each cell confirmed in 3 moves, look at their four neighbors. If any of these are unconfirmed empty cells, confirm them as reachable in 4 moves (Figure 6).

Figure 6. Cells reachable in 4 moves are confirmed

• Repeat the above steps until no more updates can be made. This will confirm the shortest path to all reachable empty cells from the start (Figure 7). Given the constraint that the start and goal are always reachable through empty cells, the shortest path to the goal will also be known.

Figure 7. Shortest path to all reachable cells is confirmed

To implement this process efficiently, it is known to use a First-In-First-Out (FIFO) queue data structure. Of course, it is possible to solve the problem without using it. If you are not sure, it is recommended to solve it with the method you come up with. A FIFO queue is a data structure with the following functions:

• Push: Adds data to the end of the queue.
• Pop: Retrieves data from the front of the queue.

Using this data structure, you can add the confirmed cells to the queue at the moment of their confirmation and then repeatedly perform Pop to check the four neighbors of the retrieved cell (i.e., process them in the order they were added), which allows for a concise implementation.

Input Format

The input is given from the standard input in the following format:

$R\ C$ $sy\$ $gy\$ $c_{(1,1)}c_{(1,2)}\ …\ c_{(1,C)}$ $c_{(2,1)}c_{(2,2)}\ …\ c_{(2,C)}$ : $c_{(R,1)}c_{(R,2)}\ …\ c_{(R,C)}$

• The first line contains the number of rows $ R(1≦R≦50) $ and the number of columns $ C(1≦C≦50) $, separated by spaces.
• The second line contains the coordinates $ (sy,sx) $ of the start point, separated by spaces. This means the start point is at row $ sy $ and column $ sx $. It holds that $ 1≦sy≦R $ and $ 1≦sx≦C $.
• The third line contains the coordinates $ (gy,gx) $ of the goal point, separated by spaces. This means the goal point is at row $ gy $ and column $ gx $. It holds that $ 1≦gy≦R $ and $ 1≦gx≦C $, and it is guaranteed that $ (gy,gx)≠(sy,sx) $.
• From the fourth line to the $ R $th line, a string of length $ C $ is given for each line. Each character is either . or #, where . indicates an empty cell and # indicates a wall cell. For the $ i $th line $ (1≦i≦R) $, the $ j $th character $ (1≦j≦C) $ represents the cell at $ (i,j) $.
• The board is surrounded by wall cells. That is, for any cell $ (i,j) $ where $ i=1, i=R, j=1, or j=C $, $ c_{(i,j)} $ is #. Also, the start and goal points are always empty cells, and it is guaranteed that you can reach the goal from the start by following empty cells.

Output Format

• Output the minimum number of moves required to move from the start point to the goal point in one line. Do not forget to add a newline at the end.

Sample Input and Output

Sample Input #1

7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########

Sample Output #1

11

Sample Input #2

5 8
2 2
2 4
########
#.#....#
#.###..#
#......#
########

Sample Output #2

10

Sample Input #3

50 50
2 2
49 49
##################################################
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
##################################################

Sample Output #3

94

Notes/Hints

Sample Explanation 1

This is the example in the problem statement.

Sample Explanation 2

You can reach the goal in 10 moves by moving as shown in Figure 8 (S represents the start, G represents the goal).

Figure 8. Path to achieve the minimum of 10 moves in Sample Input #2

Sample Explanation 3

This is merely a large open space, and it's debatable whether it can still be called a maze. In this problem, however, such a board is treated as a maze. In any case, the shortest path from the start to the goal is 94 moves.

见题面 Input 部分

见题面 Output 部分