1 条题解

  • 0
    @ 2026-9-29 15:46:00

    题意简述:

    给定一 n×10n×10 的矩阵,若有大小 ≥k\ge k 的联通块则同时赋值为空,紧接着整个矩阵同时向下掉落,求最终矩阵的状态。

    题目解法:

    显而易见,这道题可以分成消除和掉落两个部分。
    先看消除怎么消除,由于题目说了连通块能消除当且仅当它的联通块大小 ≥k\ge k,所以我们先处理出每个连通块的大小,然后再消除,具体可以用 dfs 配合 vis 数组实现。
    再看掉落如何处理,我们从下往上循环,从左往右考虑,如果下面没有东西就把这个位置上的数挪到下面的位置,具体详见代码。

    正确代码:

    #include<bits/stdc++.h> 
    using namespace std;
    inline int read(){
        int res=0;
        char c;
        bool zf=0;
        while(((c=getchar())<'0'||c>'9')&&c!= '-');
        if(c=='-')zf=1;
        else res=c-'0';
        while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
        if(zf)return -res;
        return res;
    }
    int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
    int n,p;
    int dta[105][105];
    bool vis[105][105];
    int cnt;
    void dfs(int x,int y){
    	vis[x][y]=1;
    	++cnt;
    	for(register int i=0;i<4;++i){
    		int xx=x+dx[i],yy=y+dy[i];
    		if(xx<1||xx>n||yy<1||yy>10||vis[xx][yy]||dta[xx][yy]!=dta[x][y])continue;
    		dfs(xx,yy);
    	}
    	return;
    }
    void _clear(int x,int y){
    	vis[x][y]=1;
    	for(register int i=0;i<4;++i){
    		int xx=x+dx[i],yy=y+dy[i];
    		if(xx<1||xx>n||yy<1||yy>10||vis[xx][yy]||dta[xx][yy]!=dta[x][y])continue;
    		_clear(xx,yy);
    	}
    	dta[x][y]=0;
    	return;
    }
    inline bool _remove(){
    	bool f=0;
    	for(register int i=1;i<=n;++i)
    		for(register int j=1;j<=10;++j){
    			if(dta[i][j]){
    				cnt=0;
    				memset(vis,0,sizeof(vis));
    				dfs(i,j);
    				if(cnt>=p){
    					f=1;
    					memset(vis,0,sizeof(vis));
    					_clear(i,j);
    				}
    			}
    		}
    	return f;
    }
    inline void fall(){
    	bool f=1;
    	while(f){
    		f=0;
    		for(register int i=n-1;i>=1;--i)
    			for(register int j=1;j<=10;++j){
    				if(dta[i][j]&&!dta[i+1][j]){
    					dta[i+1][j]=dta[i][j];
    					dta[i][j]=0;
    					f=1;
    				}
    			}
    	}
    	return;
    }
    signed main(){
    	n=read(),p=read();
    	for(register int i=1;i<=n;++i)
    		for(register int j=1;j<=10;++j){
    			char c;
    			while((c=getchar())<'0'||c>'9');
    			dta[i][j]=c-'0';
    		}
    	while(_remove()){
    		fall();
    	}
    	for(register int i=1;i<=n;puts(""),++i)
    		for(register int j=1;j<=10;++j){
    			putchar(dta[i][j]+'0');
    		}
    	return 0;
    }
    

    如果您没有看懂这篇题解,可以在评论区问我,我将会回答您的问题并且修改这篇题解,使它变得更加通俗易懂,服务更多的 OIer\text{OIer}。
    如果您看懂了这篇题解,可以点个赞,使这篇题解的排名上升,服务更多的 OIer\text{OIer}。

    • 1

    信息

    ID
    6780
    时间
    1000ms
    内存
    128MiB
    难度
    9
    标签
    递交数
    94
    已通过
    6
    上传者