#2149. [2012 安徽省] 挑战算周长(perimeter)

[2012 安徽省] 挑战算周长(perimeter)

题目描述

卡卡西快速的解决了超市排队的问题,受到邻居们的赞许,高兴的回到家,把糖给了妈妈,吃了香喷喷的午饭,又睡了一个甜甜的午觉,感觉人生真美好。下午爸爸回到家,听说了卡卡西帮老师及邻居们解决了难题,准备带她去游乐场玩她平日最喜欢玩的跳舞机作为奖励,卡卡西听了,兴奋的一蹦三尺高。

游乐场里人头攒动,每台跳舞机前都围满了人,怎么办呢?人这么多,想玩上估计要等好久了,卡卡西左顾右盼,突然发现一台跳舞机前面没人,“哈哈,被我发现一台没人的,赶快去……”,结果到了面前才发现这台新机器的玩法与众不同,脚下的格子随机位置显示出很多的X,踩到一个格子,就要根据规则先算出它对应的周长,然后把正确周长输入机器,最后的胜利者还可以获得游乐城的免费游戏券一张,卡卡西心动了,小朋友们,你们可以帮助卡卡西顺利拿到游戏券么?

游戏规则如下:新跳舞机踏板上有许多要分析的目标,由脚踩确定一个目标。目标边界的周长是一个有用的测量参数。编程任务:确定选中目标的周长。

新跳舞机的踏板是一个矩形的网格,里面有点 .,表示空的地方;有大写字母 X,表示目标的一部分。

方格中的一个 X 是指一个完整的网格方形区域,包括其边界和目标本身。网格中心的 X 与其边界上 88 个方向的 X 都是相邻的。任何两个相邻的 X,其网格方形区域在边界或拐角处是重叠的,所以它们的网格方形区域是相邻的。一个目标是由一系列相邻 X 的网格方形区域连接起来构成的。卡卡西总是能踩到一个 X,以选中包含该 X 的目标,记录脚踩时的坐标。行列号是从左上角开始,从 11 开始编号的。一个有用的统计参数是目标的周长。假定每个 X 的每条边上有一个方形的单元。目标中不会包含任何完全封闭的孔。

输入格式

M+1M+1 行,第一行为四个正整数 M(1M20),N(1N20),X(1XM),Y(1YN)M(1≤M≤20),N(1≤N≤20),X(1≤X≤M),Y(1≤Y≤N)(中间用空格隔开),表示网格的大小为 MM 行,NN 列,且踩中网格的第 XX 行第 YY 列方格。后面就是 MM 行,由字符.X构成。

输出格式

共一行,表示选中目标的周长。

样例

输入#1

2 2 2 2
XX
XX

输出#1

8

输入#2

6 4 2 3
.XXX
.XXX
.XXX
...X
..X.
X...

输出#2

18

数据范围

30%的数据 1N101M101≤N≤10,1≤M≤10

100%的数据 1N201M201≤N≤20,1≤M≤20