1.闭合不规则的图形面积(简单)
使用bfs算法遍历外围端点并标记,最后找没被标记的个数即是面积。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct site
{
int x,y;
}s,now,det;
queue<site>q;
int a[12][12],num=0;
bool first;
int detx[10]={-1,1,0,0};
int dety[10]={0,0,-1,1};
//上(-1,0)
//下(+1,0)
//左(0,-1)
//右(0,+1)
void input()
{
for(int i=1;i<=10;i++)
{
for(int j=1;j<=10;j++)
{
scanf("%d",&a[i][j]);
}
}
}
void solve()
{
now.x=0;
now.y=0;
q.push(now);
a[now.x][now.y]=1;
while(!q.empty())
{
det=q.front();
q.pop();
for(int i=0;i<4;i++)
{
now.x=det.x+detx[i];
now.y=det.y+dety[i];
if(now.x>=0&&now.x<=11&&now.y>=0&&now.y<=11)
{
if(a[now.x][now.y]==0)
{
q.push(now);
a[now.x][now.y]=1;
}
}
}
}
for(int i=1;i<=10;i++)
{
for(int j=1;j<=10;j++)
{
if(a[i][j]==0)
{
num++;
}
}
cout<<endl;
}
printf("%d",num);
exit(0);
}
int main()
{
input();
solve();
}
2.规则特殊图形
比如正三角形,正方形
像规则的图形一般可以使用DP的用法
具体解析可见我的坐标DP
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3000;
int n,ans,cnt;
char g[N][N];
int f[N][N],c[N][N];
int main()
{
cin>>n;
for(int i=1;i<=N-1;i++)
{
for(int j=1;j<=N-1;j++)
{
g[i][j]='1';
}
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=(n-i)*2+i;j++)
{
cin>>g[i][j];
if(g[i][j]=='1')
{
cnt++;
}
}
}
if(cnt==n*(n*2)/2)
{
cout<<0;
exit(0);
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=(n-i)*2+i;j++)
{
if(g[i][j]=='0'&&g[i-1][j-1]=='0'&&g[i-1][j]=='0'&&g[i-1][j+1]=='0')
{
// cout<<i<<" "<<j;
int num=0x3f3f3f3f;
num=min(f[i-1][j-1],num);
num=min(f[i-1][j],num);
num=min(f[i-1][j+1],num);
f[i][j]=max(f[i][j],num+1);
}
}
}
for(int i=n;i>=1;i--)
{
for(int j=i;j<=(n-i)*2+i;j++)
{
if(g[i][j]=='0'&&g[i+1][j-1]=='0'&&g[i+1][j]=='0'&&g[i+1][j+1]=='0')
{
int num=0x3f3f3f3f;
num=min(c[i+1][j-1],num);
num=min(c[i+1][j],num);
num=min(c[i+1][j+1],num);
c[i][j]=max(c[i][j],num+1);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=(n-i)*2+i;j++)
{
if((j-i+1)&1)
{
// cout<<i<<" "<<j<<" ";
ans=max(ans,f[i][j]);
}
if((j-i+1)%2==0)
{
ans=max(ans,c[i][j]);
}
}
// cout<<endl;
}
// cout<<ans<<" ";
int s=(ans+1)*(1+(ans+1)*2-1)/2;
cout<<s;
}
3.规则的矩形
同样可使用DP的用法,这里推荐悬线法DP
详细可见传送门
标签:cnt,int,面积,namespace,解决,图形,now,DP From: https://www.cnblogs.com/zhengchenxi/p/18027562