題目描述

鐵達尼克號遇險了，它發出了求救信號。距離最近的哥倫比亞號收到了訊息。時間就是生命，它必須儘快趕到鐵達尼克號遇險的地方。哥倫比亞要獲取了一張海洋圖，這張海洋圖上劃分成了n*n個比較小的單位，用1表示陸地， 用0表示海洋。船隻能從一個格子移到相鄰的4個格子裡。 為了儘快趕到出事地點，哥倫比亞號最少要走多少距離。

輸入格式

第一行，n (n<=1000)

以下的n*n行為一個0，1矩陣，表示海洋地圖
最後一行為4個小於n的整數， 表示 哥倫比亞號 和 鐵達尼克號 的座標 (x,y)

輸出格式

哥倫比亞號到鐵達尼克號的最短距離 ，答案精確到整數。

Samples

3
001
101
100
1 1 3 3

4

原始資料

• Zero1 題號：b418
• Hydro 題號：Z1418
• Locale：zh_CN
• Display：open