DS图—图非0面积/bfs【数据结构】

DS图—图非0面积

题目描述
编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示，在10*10的二维数组中，"1"围住了15个点，因此面积为15。

提示：queue

输入
测试次数t
每组测试数据格式为：
数组大小m,n
一个由0和1组成的m*n的二维数组

输出
对每个二维数组，输出符号"1"围住的"0"的个数，即围成的面积。假设一定有1组成的闭合曲线，但不唯一。

输入样例1
2
10 10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
5 8
0 1 1 0 0 1 1 0
1 0 1 0 1 0 0 1
0 1 0 1 0 0 1 0
0 1 0 0 1 1 1 0
0 0 0 0 0 0 0 0

输出样例1
15
5

bfs

思路：根据题意，只有完全被1围起来的0才算，所以四个边的0都是不行的，而且其他0一旦bfs的时候碰到了四条边上的0也是不行的。遍历0并且用bfs找0

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int b[4]={0,1,0,-1};
int c[4]={1,0,-1,0};
int bfs(int a[][105],int visited[][105],int x,int y,int m,int n)
{queue<P> q;q.push({x,y});visited[x][y]=1;int num=0;while(!q.empty()){P k=q.front();q.pop();num++;x=k.first;y=k.second;for(int i=0;i<4;i++){int xx=x+b[i];int yy=y+c[i];if(a[xx][yy]==0&&!visited[xx][yy]){//碰到边肯定不行if(xx==0||xx==m-1||yy==0||yy==n-1) return -1;q.push({xx,yy});visited[xx][yy]=1;}}}return num;
}
int main()
{int t;cin>>t;for(int i=0;i<t;i++){int m,n;cin>>m>>n;int a[105][105];for(int j=0;j<m;j++){for(int k=0;k<n;k++) cin>>a[j][k];}int res=0;//记录已经被算上的0 不用重复遍历它们int allvisited[105][105]={0};for(int j=1;j<m-1;j++){for(int k=1;k<n-1;k++){//记录一次bfs的访问记录，如果这个bfs最后返回-1，则访问记录不用同步到allvisited上，否则要int visited[105][105]={0};int b;if(a[j][k]==0&&allvisited[j][k]==0&&(b=bfs(a,visited,j,k,m,n))!=-1){int w=b;res+=w;//将一次bfs访问的0同步到allvisited上for(int q=0;q<m;q++){for(int r=0;r<n;r++){if(visited[q][r]==1) allvisited[q][r]=1;}}}}}cout<<res<<endl;}return 0;
}