题目
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输入！！！
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int cnt,dir[8][2]={{1,0},{-1,0},{0,-1},{0,1},{1,1},{-1,-1},{1,-1},{-1,1}}; 4 char a[51][51]; 5 struct node 6 { 7 int x; 8 int y; 9 node(){}; 10 node(int xx,int yy) 11 { 12 x=xx,y=yy; 13 } 14 }; 15 queue<node> q; 16 queue<node> qu; 17 bool vis[51][51]; 18 void bfs(int x,int y) 19 { 20 qu.push(node(x,y)); 21 vis[x][y]=1; 22 while(!q.empty()) 23 { 24 node now=q.front(); 25 q.pop(); 26 for(int i=0;i<8;i++) 27 { 28 int tx=now.x+dir[i][0],ty=now.y+dir[i][1]; 29 if(!vis[tx][ty]&&a[tx][ty]=='X') 30 { 31 q.push(node(tx,ty)); 32 qu.push(node(tx,ty)); 33 vis[tx][ty]=1; 34 } 35 } 36 } 37 } 38 int main() 39 { 40 int n,m,x,y; 41 while(cin>>n>>m>>x>>y&&n&&m) 42 { 43 memset(vis,0,sizeof(vis)); 44 memset(a,' ',sizeof(a)); 45 cnt=0; 46 for(int i=1;i<=n;i++) 47 { 48 for(int j=1;j<=m;j++) 49 { 50 cin>>a[i][j]; 51 } 52 } 53 for(int i=0;i<=n+1;i++) 54 { 55 for(int j=0;j<=m+1;j++) 56 { 57 if(a[i][j]!='X'&&a[i][j]!='.')a[i][j]='.'; 58 } 59 } 60 q.push(node(x,y)); 61 bfs(x,y); 62 while(!qu.empty()) 63 { 64 node now=qu.front(); 65 qu.pop(); 66 for(int i=0;i<4;i++) 67 { 68 if(a[now.x+dir[i][0]][now.y+dir[i][1]]=='.')cnt++; 69 } 70 } 71 cout<<cnt<<endl; 72 } 73 return 0; 74 }