Game with Chips#754
You are a developer of a new computer game. The game takes place on a rectangular board consisting of W \times H cells. Each cell may either contain a chip or be empty (see the figure).
A key part of the game is to determine whether two chips can be connected by a path that satisfies the following conditions:
The path must consist of segments that are either vertical or horizontal lines.
The path must not pass through any other chips.
The path may partially go outside the board. For example:
The chips at coordinates and can be connected. The chips at and can also be connected. However, the chips at and cannot be connected, as any connecting path would pass through other chips.
Your task is to write a program that checks whether two chips can be connected by a path with these properties, and if possible, determines the minimal length of such a path. The path may have turns, with both ends only at the centers of the cells (or at the centers of imaginary cells outside the board). The segment between the centers of two adjacent cells has length .
The first line contains two natural numbers: is the width, is the height of the board (1 \leq W, H \leq 75). The next lines describe the board: each line contains exactly characters. An "X" (uppercase English letter) represents a chip, and a "." (dot) represents an empty cell. All following lines describe queries: each query consists of four natural numbers, separated by spaces, X_1, Y_1, X_2, Y_2, where 1 \leq X_1, X_2 \leq W, 1 \leq Y_1, Y_2 \leq 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 ). It is guaranteed that these coordinates are different (except possibly in the last query; see below). The last line contains a query with four zeros; do not process this query. The number of queries does not exceed .
For each query, output one integer on a separate line: the length of the shortest path, or if no such path exists.
Example 1