U454299 世界旅行
题目背景
小A很喜欢旅行,并且喜欢长时间的旅行,这次,他打算周游世界。但是他没有多少钱而且也不善于计算,所以请你帮他计算一下他这次旅行的最少花费。
题目描述
小A现在有一份世界地图,他的计划是周游整个世界所有的大陆。世界地图由$0$、$1$构成,$1$表示陆地,$0$表示海洋。在陆地上只能向上下左右相邻格移动且**不能进入海洋**,每次移动需耗费$5$元。小A也可以选择购买机票,乘坐飞机。飞机起飞地点为小A当前坐标,着陆地点随意但**不能在海洋上**。假设起飞地点为$(x_1,y_1)$,着陆地点为$(x_2,y_2)$,则机票价格为$100\times((x_1-x_2)^2+(y_1-y_2)^2)$。
输入格式
输入两个整数$n$与$m$,表示世界地图的行数与列数。\
随后输入两个整数$x$与$y$,表示小A的初始位置($(1,1)$表示世界地图左上角且小A初始位置保证在陆地上)。\
下面$n$行每行输入$m$个字符,只包含$0$与$1$,表示世界地图。
输出格式
一个整数,表示小A要周游世界的最小花费。
说明/提示
大陆指的是在地图中连起来(上下左右相邻)的陆地。例如以下地图有4块大陆(用不同颜色表示)\
${\color{red}11}0{\color{blue}11}0{\color{green}1}$\
${\color{red}111}0000$\
${\color{red}11}0000{\color{brown}1}$\
${\color{red}1}0000{\color{brown}11}$\
$0{\color{brown}11111}0$
**样例2解释**:全世界只有一块大陆,小A不用花费任何钱就可以游遍所有大陆。
数据规模:$1\le n,m\le 12$,$1\le x\le n$,$1\le y\le m$