Game with Chips
You are a developer working on a new computer game. The game is set on a rectangular board made up of W×H cells. Each cell may contain a chip or be empty (refer to the figure).
A crucial aspect of the game is determining whether two chips are connected by a path that adheres to the following conditions:
The path must consist of vertical and horizontal line segments.
The path must not intersect any other chips.
Part of the path may extend outside the board. For example:
The chips at coordinates (1, 3) and (4, 4) can be connected. Similarly, the chips at (2, 3) and (5, 3) can also be connected. However, the chips at (2, 3) and (3, 4) cannot be connected because any path between them would cross other chips.
Your task is to write a program that checks if two chips can be connected by a path that meets the specified criteria and, if possible, determines the minimum length of such a path. The path is assumed to have bends, starting and ending only at the centers of the cells (or "imaginary cells" located outside the board), with the segment connecting the centers of two adjacent cells having a length of 1.
Input
The first line of the input contains two natural numbers: W – the width of the board, and H – the height of the board (1 ≤ W, H ≤ 75). The next H lines describe the board: each line consists of exactly W characters, where "X" (uppercase English letter) represents a chip, and "." (dot) represents an empty space. The subsequent lines contain the queries: each query consists of four natural numbers, separated by spaces – X_1, Y_1, X_2, Y_2, where 1 ≤ X_1, X_2 ≤ W, 1 ≤ Y_1, Y_2 ≤ H. Here, (X_1, Y_1) and (X_2, Y_2) are the coordinates of the chips to be connected (the top-left cell has coordinates (1, 1)). It is guaranteed that these coordinates will not be the same (except for the last query; see below). The last line contains a query with four zeros; this query should not be processed. The number of queries does not exceed 20.
Output
For each query, output one integer on a separate line – the length of the shortest path, or 0 if no such path exists.