Xây đường hầm

Cho một hành tinh phẳng dạng lưới ô vuông kích thước $n\times n$, các hàng và cột được đánh số từ $1$ đến $n$. Ô ở giao của hàng $r$ và cột $c$ được ký hiệu là $(r,c)$. Mỗi ô hoặc là đất, hoặc là nước.

Alice đang ở ô đất $(r_1,c_1)$ và muốn đi tới ô đất $(r_2,c_2)$. Mỗi bước, cô có thể di chuyển sang một ô kề cạnh theo một trong bốn hướng (lên, xuống, trái, phải), nhưng chỉ được đi trên ô đất (không thể đi qua ô nước).

Vì vậy hành trình của Alice có thể bất khả thi. Để giúp cô, bạn được phép xây nhiều nhất một đường hầm nối hai ô đất bất kỳ. Đường hầm cho phép đi tự do giữa hai đầu của nó. Chi phí xây đường hầm nối hai ô $(r_s,c_s)$ và $(r_t,c_t)$ là:

$$(r_s-r_t{)}^2+(c_s-c_t{)}^2$$

Hãy tìm chi phí nhỏ nhất để xây nhiều nhất một đường hầm sao cho Alice có thể đi từ $(r_1,c_1)$ tới $(r_2,c_2)$. Nếu không cần xây đường hầm nào thì chi phí là $0$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, kích thước lưới.
• Dòng thứ hai chứa hai số nguyên $r_1$ và $c_1$, ô Alice đang đứng.
• Dòng thứ ba chứa hai số nguyên $r_2$ và $c_2$, ô Alice muốn tới.
• $n$ dòng tiếp theo, mỗi dòng là một xâu gồm $n$ ký tự. Ký tự thứ $j$ của dòng thứ $i$ là 0 nếu ô $(i,j)$ là đất, hoặc 1 nếu là nước.

Đảm bảo $(r_1,c_1)$ và $(r_2,c_2)$ đều là ô đất.

Dữ liệu ra

In ra một số nguyên là chi phí nhỏ nhất để Alice có thể đi từ $(r_1,c_1)$ tới $(r_2,c_2)$.

Ràng buộc

• $1\le n\le 50$
• $1\le r_1,c_1,r_2,c_2\le n$

Ví dụ