3 条题解

  • 1
    @ 2024-12-19 19:32:05
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e6+10;
    char a[210][210];
    int st[210][210];
    int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
    	int n,m;
    void axx()
    {
    	int ans=0;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)st[i][j]=0;
    	}
    	for(int i=1;i<=n;i++)
    		 {
    		 	for(int j=1;j<=m;j++)
    		 	{
    			if(st[i][j]||a[i][j]=='*')continue;
    			 ans++;
    			 queue<pair<int,int>>p;
    			 int sx=n+1,sy=m+1,mx=0,my=0;
    			 p.push({i,j});
    			 st[i][j]=ans;
    			 while(p.size())
    			 {
    			 	auto [x,y]=p.front();
    			 	p.pop();
    			 	sx=min(sx,x);mx=max(mx,x);
    			 	sy=min(sy,y);my=max(my,y);
    			 	for(int k=0;k<4;k++)
    			 	{
    				 int xx=x+dx[k],yy=y+dy[k];
    				 if(st[xx][yy]==ans||a[xx][yy]=='*')continue;
    				 p.push({xx,yy});
    				 st[xx][yy]=ans;	
    				}
    			 }
    			 for(int i1=sx;i1<=mx;i1++)
    			 {
    			 	for(int j1=sy;j1<=my;j1++)
    			 	{
    				 	a[i1][j1]='.';
    				 	st[i1][j1]=ans;
    			   }
    			 }	
    			}
    		 }
    }
    signed main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int t=1;
    	//cin>>t;
    	while(t--)
    	{
    		cin>>n>>m;
    		
    	 for(int i=0;i<=n+1;i++)
    	 {
    	 	a[i][0]='*';
    		a[i][m+1]='*';
    	 }
    	 for(int i=0;i<=m+1;i++)
    	 {
    	 	a[0][i]='*';
    		a[n+1][i]='*';
    	 }
    	 for(int i=1;i<=n;i++)
    	 {
    	 	for(int j=1;j<=m;j++)cin>>a[i][j];
    	 }
    	 axx();
    	 axx();
    	 for(int i=1;i<=n;i++)
    	 {
    	 	for(int j=1;j<=m;j++)cout<<a[i][j];
    	 	cout<<'\n';
    	 }
    	}
    }
    

    信息

    ID
    1096
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    141
    已通过
    22
    上传者