fuzhuo---Problem 1082 最大黑区域

朴灿烈づ我的快乐病毒、 2022-06-15 07:49 144阅读 0赞

二值图像是由黑白两种像素组成的矩形点阵，图像识别的一个操作是求出图像中最大黑区域的面积。请设计一个程序完成二值图像的这个操作。黑区域由黑像素组成，一个黑区域中的每个像素至少与该区域中的另一个像素相邻，规定一个像素仅与其上、下、左、右的像素相邻。两个不同的黑区域没有相邻的像素。一个黑区域的面积是其所包含的像素的个数。

## ![prodesc.gif][] Input ##

输入由多个测试例组成。每个测试例的第一行含两个整数n和m, (1 <=n,m<=100), 分别表示二值图像的行数与列数，后面紧跟着n行，每行含m个整数0或1，其中第i行表示图像的第i行的m个像素，0表示白像素，1表示黑像素。同一行的相邻两个整数之间用一个空格隔开，两个测试例之间用一个空行隔开，最后一个测试例之后隔一个空行，再接的一行含有两个整数0，标志输入的结束。

## ![prodesc.gif][] Output ##

每个测试例对应一行输出，含一个整数，表示相应的图像中最大黑区域的面积。

## ![prodesc.gif][] Sample Input ##

5 60 1 1 0 0 11 1 0 1 0 10 1 0 0 1 00 0 0 1 1 11 0 1 1 1 00 0

## ![prodesc.gif][] Sample Output ##

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m,map[101][101];
    int dx[]={-1,0,1,0};
    int dy[]={0,1,0,-1};
    int sum;
    void dfs(int x,int y)
    {
        map[x][y]=0;
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&map[xx][yy])
            {
                sum++;
                dfs(xx,yy);
            }
        }
    }
    int main()
    {
        while(~scanf("%d %d",&n,&m),n||m)
        {
            int maxx=0;
            sum=0;
            for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                scanf("%d",&map[i][j]);
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    if(map[i][j])
                    {
                        sum=1;
                        dfs(i,j);
                        if(sum>maxx)
                            maxx=sum;
                    }
                }
            }
            printf("%d\n",maxx);
        }
        return 0;
    }

错误的：

\#include<cstdio>  
\#include<cstring>  
\#include<algorithm>  
using namespace std;  
int n,m,map\[101\]\[101\];  
int dx\[\]=\{-1,0,1,0\};  
int dy\[\]=\{0,1,0,-1\};  
int dfs(int x,int y,int step)  
\{  
    map\[x\]\[y\]=0;  
    for(int i=0;i<4;i++)  
    \{  
        int xx=x+dx\[i\];  
        int yy=y+dy\[i\];  
        if(xx>=0&&xx<n&&yy>=0&&yy<m&&map\[xx\]\[yy\])  
        \{  
            dfs(xx,yy,step+1);  
        \}  
    \}  
    return step; //我的理解：step是dfs里面的变量，所以它是传不出来的，这里它总是1不变  
\}  
int main()  
\{  
    while(~scanf("%d %d",&n,&m),n||m)  
    \{  
        int maxx=0;  
        for(int i=0;i<n;i++)  
        for(int j=0;j<m;j++)  
            scanf("%d",&map\[i\]\[j\]);  
        for(int i=0;i<n;i++)  
        \{  
            for(int j=0;j<m;j++)  
            \{  
                if(map\[i\]\[j\])  
                \{  
                    int ans=dfs(i,j,1);  
                    if(ans>maxx)  
                        maxx=ans;  
                \}  
            \}  
        \}  
        printf("%d\\n",maxx);  
    \}  
    return 0;  
\}

[prodesc.gif]: http://acm.fzu.edu.cn/image/prodesc.gif