Topic background

Yyy2015c01 quickly solved the problem, was praised by the neighbors, happily returned home, gave the sugar to my mother, had a delicious lunch and took a sweet nap. I feel that life is really beautiful. In the afternoon, my father came home and heard that yyy2015c01 had helped the teacher and neighbors solve their problems. He was going to take her to the playground to play her favorite dance machine as a reward. Yyy2015c01 jumped three feet high with excitement.

Title Description

The playground is crowded, and everyone is surrounded by people in front of each dancing machine. What should I do? There are so many people. It's estimated that it will take a long time to play. Yyy2015c01 looked around and suddenly found that there was no one in front of a dancing machine, "ha ha, I found one empty, hurry up...". As a result, I found that the playing method of the new machine was different. The random position of the grid under my feet showed a lot of "X", stepping on a grid, It is necessary to calculate its corresponding circumference according to the rules, and then input the correct circumference into the machine. The final winner can also get a free game ticket of the amusement city. Yyy2015c01 is excited. Children, can you help yyy2015c01 get the game ticket smoothly?

The rules of the game are as follows:

There are many targets to analyze on the pedal of the new dance machine. One target is determined by stepping on it. The perimeter of the target boundary is a useful measurement parameter. Programming task: determine the perimeter of the selected target. The pedal of the new dance machine is a rectangular grid, with points inside, Indicates an empty place; There is a capital X # part of the target.

An "X" in a grid refers to a complete grid square area, including its boundary and the target itself. The ＾ x ＾ in the center of the grid is adjacent to ＾ x ＾ in 88 ＾ directions on its boundary. The grid square areas of any two adjacent {x overlap at the boundary or corner, so their grid square areas are adjacent. A target is composed of a series of adjacent grid square areas. In grid 11 ， one target fills all grids; There are two targets in the grid ， 22 ， one of which only occupies a grid square area in the lower left corner, and the other ， x ， belongs to the other target.

yyy2015c01 can always step on an "X" to select the target containing the "X" and record the coordinates when stepping on it. Row and column numbers are numbered from the top left corner and from # 11 #. A useful statistical parameter is the perimeter of the target. Suppose that there is a square cell on each side of each ＾ x ＾.

The target does not contain any completely closed holes.

Input format

A total of ＾ M+1M+1 ＾ rows. The first row is four positive integers ＾ M,N,X,YM,N,X,Y (separated by spaces), indicating that the size of the grid is ＾ MM ＾ row, NN ＾ column, and step on the square of ＾ XX ＾ row, YY ＾ column of the grid. This is followed by the ， MM ， line, which consists of characters And ＾ X ＾.

Output format

A total of one line indicates the perimeter of the selected target.

Sample input and output

Enter #1 copy

2 2 2 2 
XX
XX

Output #1 copy

8

Enter #2 copy

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

Output #2 copy

18

Description / tips

1\leq M\leq 201≤M≤20，1\leq N\leq 201≤N≤20，1\leq X\leq M1≤X≤M，1\leq Y\leq N1≤Y≤N.

#include <stdio.h>
#include <string.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#pragma warning(disable:4996)
using namespace std;
//Summary bfs
//Use bfs to find the connected block, and then write a check function to calculate the side length
typedef long long ll;
int m = 0;
int n = 0;
int sx = 0;
int sy = 0;
int ans = 0;
char maze[66][66];
int vis[66][66];
int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dy[] = { 1,1,0,-1,-1,-1,0,1 };
int dx1[] = { 0,1,0,-1 };
int dy1[] = { 1,0,-1,0 };
int check(int x, int y)
{
	int i = 0;
	int num = 0;
	for (i = 0; i < 4; i++)
	{
		int tx = x + dx1[i];
		int ty = y + dy1[i];
		if (maze[tx][ty] != 'X')
		{
			num++;
		}
	}
	return num;
}
void bfs()
{
	queue<pair<int, int>> q;
	q.push(make_pair(sx, sy));
	vis[sx][sy] = 1;
	ans += check(sx, sy);
	while (q.size())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		int i = 0;
		for (i = 0; i < 8; i++)
		{
			int tx = x + dx[i];
			int ty = y + dy[i];
			if (tx < 1 || tx >m || ty <1 || ty >n || maze[tx][ty] != 'X' || vis[tx][ty] == 1)
			{
				continue;
			}
			q.push(make_pair(tx, ty));
			vis[tx][ty] = 1;
			ans += check(tx, ty);
		}
	}
	cout << ans;
}
int main()
{
	cin >> m >> n >> sx >> sy;
	int i = 0;
	int j = 0;
	for (i = 1; i <= m; i++)
	{
		for (j = 1; j <= n; j++)
		{
			cin >> maze[i][j];
		}
	}
	bfs();

}