建网站报价,网站查询ip,优化营商环境个人心得体会,济南正规网站建设公司哪家好DS图—图非0面积
题目描述 编程计算由1围成的下列图形的面积。面积计算方法是统计1所围成的闭合曲线中0点的数目。如图所示#xff0c;在10*10的二维数组中#xff0c;1围住了15个点#xff0c;因此面积为15。
提示…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
#includebits/stdc.h
using namespace std;
typedef pairint,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)
{queueP q;q.push({x,y});visited[x][y]1;int num0;while(!q.empty()){P kq.front();q.pop();num;xk.first;yk.second;for(int i0;i4;i){int xxxb[i];int yyyc[i];if(a[xx][yy]0!visited[xx][yy]){//碰到边肯定不行if(xx0||xxm-1||yy0||yyn-1) return -1;q.push({xx,yy});visited[xx][yy]1;}}}return num;
}
int main()
{int t;cint;for(int i0;it;i){int m,n;cinmn;int a[105][105];for(int j0;jm;j){for(int k0;kn;k) cina[j][k];}int res0;//记录已经被算上的0 不用重复遍历它们int allvisited[105][105]{0};for(int j1;jm-1;j){for(int k1;kn-1;k){//记录一次bfs的访问记录如果这个bfs最后返回-1则访问记录不用同步到allvisited上否则要int visited[105][105]{0};int b;if(a[j][k]0allvisited[j][k]0(bbfs(a,visited,j,k,m,n))!-1){int wb;resw;//将一次bfs访问的0同步到allvisited上for(int q0;qm;q){for(int r0;rn;r){if(visited[q][r]1) allvisited[q][r]1;}}}}}coutresendl;}return 0;
}
