【题解】Image Perimeters-C++

谁借莪１个温暖的怀抱￠ 2021-10-18 07:58 217阅读 0赞

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

转载于:https://www.cnblogs.com/moyujiang/p/11213502.html