Skip to content

1425: イレイナ圈结界

题目

题目描述

伊蕾娜是一位魔女,因为向往着幼时读过的旅行故事,她踏上了漫长的旅途,与形形色色的国家与人们邂逅。

这一次,她来到了一个常年遭到野兽袭击的国家,为了感谢国王的款待,她决定帮这个国家创造一个可以抵御野兽入侵的结界。

伊蕾娜得到了一张绘制着 $n\times m$ 的区域的地图,其中 'X' 的区域表示着这个国家的领土(保证为一个连通块),'.' 代表着一些空地。

由于这个国家过于庞大,伊蕾娜想要创造结界必须绕这个国家的领土完整的一周最后回到起点。于是她在地图上的一个地方画下了 '*' 并决定从这里出发。

伊蕾娜的法杖可以帮助她在单位时间内移动到地图上与当前所在位置相连的八个格子中的一个,现在她想知道她从起点出发最少经过多少个格子就能绕这个国家一周(只要轨迹能包围国家即可,不需要紧贴着走),你能帮帮她吗?

输入格式

第一行两个整数 $n, m$ 表示地图的大小。

接下来 $n$ 行 $m$ 列表示一个地图。

输出格式

输出一个整数,表示伊蕾娜从起点出发最少经过多少个格子就能绕这个国家一周,保证有解。

样例输入

text 6 7 ....... ...X... ..XXX.. ...XXX. ...X... ......*

样例输出

text 13

数据范围

对于 $40\%$ 的数据,$n, m\leq 12$

对于 $60\%$ 的数据,$n, m\leq 30$

对于 $100\%$ 的数据,$n, m\leq 50$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!