P3684 [CERC2016] Hangar Hurdles

You are evaluating construction plans for a giant airplane hangar. The hangar floor can be represented as an $n \times n$ grid, where each cell is either empty or contains an obstacle. Rows are numbered from $1$ to $n$ from top to bottom, and columns are numbered from $1$ to $n$ from left to right. It is important that large containers for storing airplane parts can move freely on the floor. Each container can be seen as an axis-aligned square centered at some cell. For an odd integer $k$, a container of size $k$ is a square covering $k$ rows and $k$ columns. The coordinate of a container is the coordinate of its center cell. A container can move up, down, left, or right, but it cannot touch obstacles and cannot move outside the hangar boundary. Given $q$ pairs of cells $A_k$ and $B_k$, for each pair, find the maximum size (also an odd integer) of a container that can move from $A_k$ to $B_k$.

The first line contains a positive integer $n$ ($2 \le n \le 1000$), the size of the hangar. The next $n$ lines each contain $n$ characters describing the hangar, where `.` denotes an empty cell and `#` denotes an obstacle. The next line contains a positive integer $q$ ($1 \le q \le 300000$), the number of queries. Each of the next $q$ lines contains four positive integers $A_x, A_y, B_x, B_y$ ($1 \le A_x, A_y, B_x, B_y \le n$), the coordinates of $A$ and $B$. It is guaranteed that $A$ and $B$ are distinct empty cells.

Output $q$ lines, each with one integer. For each query, output the maximum size. If no solution exists, output $0$.

Translated by ChatGPT 5