题目描述
在一个群岛上,有一个富可敌国的大富翁。他打算在这个群岛上建造一个最大城堡,也就是群岛上最大的岛屿。
输入
第一行是一个整数T,代表测试数据的组数。每组数据中第一行是两个整数n,m,代表地图的大小。接下来n行每行共m个整数。0代表海洋,1代表陆地。其中T<=50,n,m<=200
输出
共T行,最大的面积。
样例输入
1 5 5 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0
样例输出
8
上一篇博客写了深度优先搜索求区域的块数,这篇代码就拿上一篇博客的代码稍微改了一下,求区域的最大面积。
#include<bits/stdc++.h> using namespace std; int n,m; const int maxn=1000; int a[maxn][maxn]; int inq[maxn][maxn]; int X[4]={0,0,1,-1}; int Y[4]={1,-1,0,0}; struct node{ int x; int y; }Node; bool judge(int x,int y){ if(x<0||x>=n||y<0||y>=m)return false; if(inq[x][y]==1||a[x][y]==0)return false; return true; } int bfs(int x,int y){ int area=0; queue<node>s; Node.x=x,Node.y=y; s.push(Node); inq[x][y]=true; while(s.empty()!=1){ node t=s.front(); s.pop(); area++; for(int i=0;i<4;i++){ int newx=t.x+X[i]; int newy=t.y+Y[i]; if(judge(newx,newy)){ Node.x=newx,Node.y=newy; s.push(Node); inq[newx][newy]=true; } } } return area;//返回区域的面积 } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin>>T; while(T--){ cin>>n>>m; int sum=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; inq[i][j]=false; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]==1&&inq[i][j]==0){ sum=max(sum,bfs(i,j)); } } } cout<<sum<<endl; } return 0; }
题目来源:2018年安徽省省赛
c/c++开发分享数据结构算法(求区域的最大面积)地址:https://blog.csdn.net/tutoua/article/details/107910300
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598137.html