比赛 NOIP2023模拟赛4 评测结果 AAAWWWEEEE
题目名称 雪花 最终得分 30
用户昵称 yuanna 运行时间 0.847 s
代码语言 C++ 内存使用 11.85 MiB
提交时间 2023-11-16 09:17:07
显示代码纯文本
#include <bits/stdc++.h> 
using namespace std;
char a;
int W,H,num=0,nl[501]={},nr[501]={},n[501]={},maxn=-1145141,maxi=1,langle=0,rangle=0;
bool xue[501][50001]={};
void left(int x,int y,int root,int numl)
{
 if(xue[x][y]==1)
 numl=numl+1;
 if(x!=1&&y!=1)
 left(x-1,y-1,root,numl);
 else
 nl[root]=numl;
}
void right(int x,int y,int root,int numr)
{
 if(xue[x][y]==1)
 numr=numr+1;
 if(x!=1&&y!=W)
 right(x-1,y+1,root,numr);
 else
 nr[root]=numr;
}
int main()
{
 freopen("snow.in","r",stdin);
 freopen("snow.out","w",stdout);
 cin>>W>>H;
 for(int i=1;i<=W;i++)
  for(int j=1;j<=H;j++)
   {
    cin>>a;
    if(a=='*')
    {
     xue[i][j]=1;
     num=num+1;
    }
    else
    if(a=='-')
    xue[i][j]=0;
   }
 for(int i=2;i<=W;i++)
 {
  left(H,i-1,i,0);
  right(H,i,i,0);
  n[i]=n[i-1]+nr[i]-nl[i];
 }
 for(int i=1;i<=W;i++)
 {
  if(n[i]>maxn)
  {
   maxn=n[i];
   maxi=i;
  }
 }
 for(int i=2;i<=maxi;i++)
 langle=langle+nl[i];
 for(int i=maxi+1;i<=W;i++)
 rangle=rangle+nr[i];
 cout<<num-rangle-langle;
 return 0;
 
 
 
 
 
 
 
 
 
}