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$