Minimum Moves to Meet on a Grid

Two players are placed on a grid with obstacles. Each cell of the grid is either empty (denoted by '.') or blocked (denoted by 'W'). The players can move in four directions: up, down, left, and right. Given the grid and the 1-indexed starting positions of both players, your task is to determine the minimum total number of moves required so that the players can meet at some common cell. If there is no cell that both players can reach, print \( -1 \).

The total number of moves is computed as the sum of the moves required from player A to the meeting point and from player B to the meeting point.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 grid_line_1
 grid_line_2
 ...
 grid_line_n
 startA_x startA_y
 startB_x startB_y

where n is the number of rows and m is the number of columns. Then n lines follow, each representing a row of the grid. The next line contains the coordinates for player A and the following line contains the coordinates for player B. All coordinates are 1-indexed.

outputFormat

Output a single integer denoting the minimum number of moves required for the two players to meet. If it is impossible for them to meet, output -1.

5 5
.....
.WWWW
.....
.WWWW
.....
1 1
5 5

8