Hi there,
I done pre-computation like filling connected component (vector v) and component id(vector v1) and then computing max expand pond. My code complexity is O(n*m)
"#include<bits/stdc++.h>
using namespace std;
int k=1;
int backt(int i,int j,vector<vector> &v,vector<vector> &v1,int n,int m)
{
if(i>=n || j>=m || i<0 || j<0 || v[i][j]==0|| v1[i][j]!=0)
return 0;
v1[i][j]=k;
int d=backt(i+1,j,v,v1,n,m);
int u=backt(i-1,j,v,v1,n,m);
int l=backt(i,j+1,v,v1,n,m);
int r=backt(i,j-1,v,v1,n,m);
return 1+d+u+l+r;
}
void fill(int i,int j,vector<vector> &v,int c,int n,int m)
{
if(i>=n || j>=m || i<0 || j<0 || v[i][j]!=1)
return;
v[i][j]=c;
fill(i+1,j,v,c,n,m);
fill(i-1,j,v,c,n,m);
fill(i,j+1,v,c,n,m);
fill(i,j-1,v,c,n,m);
return;
}
int main()
{
int maxx=0;
int n,m;
cin>>n>>m;
vector<vector> v(n,vector(m,0)),v1(n,vector(m,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>v[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(v[i][j]==1 && v1[i][j]==0)
{
int c=backt(i,j,v,v1,n,m);
fill(i,j,v,c,n,m);
k++;
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(v[i][j]==0)
{
int c=1;
map<int,int> m1;
if((i-1)>=0 && m1[v1[i-1][j]]==0)
{
c+=v[i-1][j];
m1[v1[i-1][j]]=1;
}
if((i+1)<n && m1[v1[i+1][j]]==0)
{
c+=v[i+1][j];
m1[v1[i+1][j]]=1;
}
if((j-1)>=0 && m1[v1[i][j-1]]==0)
{
c+=v[i][j-1];
m1[v1[i][j-1]]=1;
}
if((j+1)<m && m1[v1[i][j+1]]==0)
{
c+=v[i][j+1];
m1[v1[i][j+1]]=1;
}
maxx=max(c,maxx);
}
}
}
cout<<maxx;
}"