题目背景
闲着没事逛逛wiki，发现ml13这道题居然挂了一次
诶~正好没写过~
5 minutes later
一次性A掉了，于是来发一篇题解
题目大意
这道题目和细胞很像，传送门：https://www.wikioi.cn/problem/10083
在一个n*n的矩阵中，选出一块连续的区域，区域满足一下要求：
·组成区域的数必须相同
求这个区域的最大面积，还有组成这个区域的数（特殊情况不说明了）
思路分析
说是话这题数据真的很水，N只有100，实际上可以出5000的
很简单，对于矩阵的每一个元素，假设没有访问过，就进行BFS，将周围相同的元素全部访问，统计大小
再将每一个访问过的元素打上标记
因为每个元素会也只会访问一次，所以时间复杂度是妥妥的O（n*n）
CODE
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long maxn=1e3+10;
bool vis[maxn][maxn];
int n,ans=-1,id=-1;
int a[maxn][maxn];
int walk[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
queue <pair<int,int> > q;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int cnt = 0;
q.push(make_pair(i,j));
vis[i][j] = 1;
while(!q.empty()){
int u = q.front().first;
int v = q.front().second;
q.pop();
cnt++;
for(int k=0;k<=3;k++){
int nx = u+walk[k][0];
int ny = v+walk[k][1];
if(nx <= 0 || ny <= 0 || nx > n || ny > n) continue;
if(a[u][v] != a[nx][ny]) continue;
if(vis[nx][ny])continue;
vis[nx][ny] = 1;
q.push(make_pair(nx,ny));
}
}
if(cnt > ans){
ans = cnt;
id = a[i][j];
}
else if(cnt == ans){
if(id < a[i][j]){
id = a[i][j];
}
}
}
}
cout<<ans<<endl<<id<<endl;
return 0;
}
共 1 条回复
那是我做的，之前我没有帐号，于是 ml13 就借我帐号用了一下，我给这题 WA 了