Shortest Path on Grid (Easy)

2 secs 1024 MB
michirakara's icon michirakara

縦にNN個、横にNN個の点が書かれたグリッドの平面GGがあります。
グリッド上のいくつかの点には11からMMのうちのどれかの数字が書かれていることがあります。
Gi,jG_{i,j}からGi,j+1G_{i,j+1}までとGi+1,jG_{i+1,j}までの距離は11とします。
11からMMまでの点をそれぞれ順番に11本の直線で結ぶ時、それぞれの線の長さの2乗の和の最小値を求めてください。
また、それぞれの数字は一つ以上あることが保証され、複数個あることもあります。

制約
1N1001\leq N\leq100
1MN21\leq M\leq N^2

入力の形式
NN MM
G0,0G_{0,0} G0,1G_{0,1} G0,N\cdots G_{0,N}
G1,0G_{1,0} G1,1G_{1,1} G1,N\cdots G_{1,N}
\vdots
GN,0G_{N,0} GN,1G_{N,1} GN,N\cdots G_{N,N}

入力例1
5 5
2 . 2 . 5
. 1 . 3 .
. . 4 . .
3 . . 2 .
. 4 . 5 .
出力例1
11

それぞれの線の長さを2乗した数の和の最小値を求めることに注意してください(MojaCoderだと誤差を許容できないので...)

入力例2
3 2
1 1 1
1 1 2
2 2 2
出力例2
1

何も書かれていない点が1つもないこともあります。

Submit


Go (1.21)