【题解】Image Perimeters-C++

发布时间：2020-12-16 07:18:41 所属栏目：百科来源：网络整理

导读：题目 Description 给出一张由"x"和".“组成的矩阵。每个"x"可以向上下左右及两个斜对角进行连通，请问由某个点开始的"x”，它所连通的图形的周长为多少。 Input 整个测试有多组数据，整个测试以四个零代表结束。对于每个数据，第一行给出整个图形的大小(长

题目
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,-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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!