題目描述

鐵達尼克號遇險了，它發出了求救信號。距離最近的哥倫比亞號收到了訊息。時間就是生命，它必須儘快 趕到鐵達尼克號遇險的地方。哥倫比亞要獲取了一張海洋圖a，這張海洋圖上劃分成了n ∗ n個比較小的單 位，用1表示陸地，用0表示海洋。船隻能從一個格子移到相鄰的4個格子裏（上，下，左，右），且船不能 移動到陸地上。哥倫比亞號位於位置(G_x, G_y)，鐵達尼克號位於位置(T_x, T_y)，為了使哥倫比亞號儘快趕 到出事地點，請求出它最少要走多少距離。

 

實現細節

你需要在標準輸入（stdin）讀入樣例，並在標準輸出（stdout）輸出答案。

輸入格式

n

a_1,1 a_1,2 a_1,3 . . . a_1,n

a_2,1 a_2,2 a_2,3 . . . a_2,n

a_3,1 a_3,2 a_3,3 . . . a_3,n

...

a_n,1 a_n,2 a_n,3 . . . a_n,n

G_x G_y T_x T_y

其中a在輸入時并無空隔間隔

輸出格式

設最短距離為d

d

Samples

3
001
101
100
1 1 3 3

4

提示

約束條件

ˆ 1 ≤ n ≤ 1000

ˆ a_i,j ∈ 0, 1

ˆ 1 ≤ G_x, G_y, T_x, T_y ≤ n

子任務

1. （100分）沒有額外的約束條件

原始資料

• Zero1 題號：b428
• Hydro 題號：Z1428
• Locale：zh_TW
• Display：open