题目
Description
给出一张由”x”和”.“组成的矩阵。每个”x”可以向上下左右及两个斜对角进行连通,请问由某个点开始的”x”,它所连通的图形的周长为多少。
Input
整个测试有多组数据,整个测试以四个零代表结束。
对于每个数据,第一行给出整个图形的大小(长度小于50),再给出开始点的坐标。接下来若干行用于描述这个图形。
Output
如题
Sample Input
2 2 2 2
XX
XX
6 4 2 3
.XXX
.XXX
.XXX
…X
…X.
X…
5 6 1 3
.XXXX.
X…X
…XX.X
.X…X
…XXX.
7 7 2 6
XXXXXXX
XX…XX
X…X…X
X…X…
X…X…X
X…X
XXXXXXX
7 7 4 4
XXXXXXX
XX…XX
X…X…X
X…X…
X…X…X
X…X
XXXXXXX
0 0 0 0
Sample Output
8
18
40
48
8
思路
这道题依然是找连通块,找到了把每一个连通块的坐标记录下来,求周长可以转换为求所有连同块四周的’.‘的数量,注意把这个图周围一圈打上’.’方便最后计算,最后的操作可以用队列来做,也可以for过一遍。
注意:这道题是while输入!!!
代码
#include<bits/stdc++.h>
using namespace std;
int cnt,dir[][]={{,},{-,},{,-},{,},{,},{-,-},{,-},{-,}};
char a[][];
struct node
{
int x;
int y;
node(){};
node(int xx,int yy)
{
x=xx,y=yy;
}
};
queue<node> q;
queue<node> qu;
bool vis[][];
void bfs(int x,int y)
{
qu.push(node(x,y));
vis[x][y]=;
while(!q.empty())
{
node now=q.front();
q.pop();
for(int i=;i<;i++)
{
int tx=now.x+dir[i][],ty=now.y+dir[i][];
if(!vis[tx][ty]&&a[tx][ty]=='X')
{
q.push(node(tx,ty));
qu.push(node(tx,ty));
vis[tx][ty]=;
}
}
}
}
int main()
{
int n,m,x,y;
while(cin>>n>>m>>x>>y&&n&&m)
{
memset(vis,,sizeof(vis));
memset(a,'\0',sizeof(a));
cnt=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=;i<=n+;i++)
{
for(int j=;j<=m+;j++)
{
if(a[i][j]!='X'&&a[i][j]!='.')a[i][j]='.';
}
}
q.push(node(x,y));
bfs(x,y);
while(!qu.empty())
{
node now=qu.front();
qu.pop();
for(int i=;i<;i++)
{
if(a[now.x+dir[i][]][now.y+dir[i][]]=='.')cnt++;
}
}
cout<<cnt<<endl;
}
return ;
}