3 条题解

  • 2
    @ 2024-12-19 20:17:14
    #include<bits/stdc++.h>
    using namespace std;
    const int N=210;
    int n,m,xi,xa,yi,ya;
    int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
    string mp[N];
    bool st[N][N];
    void dfs(int x,int y)
    {
    	for(int i=0;i<8;i++)
    	{
    		int X=x+dx[i],Y=y+dy[i];
    		if(X<0||X>=n||Y<0||Y>=m||mp[X][Y]=='*'||st[X][Y])continue;
    		xi=min(xi,X);xa=max(xa,X);
    		yi=min(yi,Y);ya=max(ya,Y);
    		st[X][Y]=true;
    		dfs(X,Y);
    	}
    }
    signed main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);cout.tie(0);
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    	{
    		cin>>mp[i];
    	}
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<m;j++)
    		{
    			if(mp[i][j]=='.'&&!st[i][j])
    			{
    				xi=i,xa=i,yi=j,ya=j;
    				st[i][j]=true;
    				dfs(i,j);
    				for(int k=xi;k<=xa;k++)
    				{
    					for(int l=yi;l<=ya;l++)
    					{
    						mp[k][l]='.';
    					}
    				}
    			}
    		}
    	}
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<m;j++)
    		{
    			cout<<mp[i][j];
    		}
    		cout<<endl;
    	}
    }
    
    • 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';
      	 }
      	}
      }
      
      • 1
        @ 2024-12-16 13:12:08

        `

        #include<bits/stdc++.h>
        #define int long long
        using namespace std;
        const int inf=0x3f3f3f3f;
        const int f=1e9+7;
        const int N=2e5+10;
        char a[205][205];
        int n,m;
        void dfs(int i,int j){
            if(a[i][j]=='.' && a[i+1][j]=='.' && a[i][j+1]=='.' && a[i+1][j+1]=='*'  && i+1<=n && j+1<=m){
                a[i+1][j+1]='.';
                dfs(i+1,j+1);
            }
            if(a[i][j]=='.' && a[i+1][j]=='*' && a[i][j+1]=='.' && a[i+1][j+1]=='.'  && i+1<=n && j+1<=m){
                a[i+1][j]='.';
                dfs(i+1,j);
            }
            if(a[i][j]=='.' && a[i+1][j]=='.' && a[i][j+1]=='*' && a[i+1][j+1]=='.'  && i+1<=n && j+1<=m){
                a[i][j+1]='.';
                dfs(i,j+1);
            }
            if(a[i][j]=='.' && a[i+1][j-1]=='*' && a[i][j-1]=='.' && a[i+1][j]=='.' && i+1<=n && j-1>=1){
                a[i+1][j-1]='.';
                dfs(i+1,j-1);
            }
            if(a[i][j]=='.' && a[i+1][j-1]=='.' && a[i][j-1]=='*' && a[i+1][j]=='.' && i+1<=n && j-1>=1){
                a[i][j-1]='.';
                dfs(i,j-1);
            }
            if(a[i][j]=='.' && a[i+1][j-1]=='.' && a[i][j-1]=='.' && a[i+1][j]=='*' && i+1<=n && j-1>=1){
                a[i+1][j]='.';
                dfs(i+1,j);
            }
            if(a[i][j]=='.' && a[i-1][j]=='.' && a[i-1][j+1]=='*' && a[i][j+1]=='.' && i-1>=1 && j+1<=m){
                a[i-1][j+1]='.';
                dfs(i-1,j+1);
            }
            if(a[i][j]=='.' && a[i-1][j]=='*' && a[i-1][j+1]=='.' && a[i][j+1]=='.' && i-1>=1 && j+1<=m){
                a[i-1][j]='.';
                dfs(i-1,j);
            }
            if(a[i][j]=='.' && a[i-1][j]=='.' && a[i-1][j+1]=='.' && a[i][j+1]=='*' && i-1>=1 && j+1<=m){
                a[i][j+1]='.';
                dfs(i,j+1);
            }
            if(a[i][j]=='.' && a[i][j-1]=='.' && a[i-1][j]=='.' && a[i-1][j-1]=='*' && i-1>=1 && j-1>=1){
                a[i-1][j-1]='.';
                dfs(i-1,j-1);
            }
            if(a[i][j]=='.' && a[i][j-1]=='.' && a[i-1][j]=='*' && a[i-1][j-1]=='.' && i-1>=1 && j-1>=1){
                a[i-1][j]='.';
                dfs(i-1,j);
            }
            if(a[i][j]=='.' && a[i][j-1]=='*' && a[i-1][j]=='.' && a[i-1][j-1]=='.' && i-1>=1 && j-1>=1){
                a[i][j-1]='.';
                dfs(i,j-1);
            }
        }
        void solve()
        {
            cin >> n >> m;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++) {
                    cin >> a[i][j];
                }
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    dfs(i,j);
                }
            }
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    cout << a[i][j];
                }
                cout << endl;
            }
        }
        void close(){
            ios::sync_with_stdio(false);
            cin.tie(0);
            cout.tie(0);
        }
        signed main ()
        {
            close();int T = 1;
        //    cin >> T;
            while(T--) solve();
            return 0;
        } //
        
        • 1

        信息

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