题意简述:
给定一 $n\times10$ 的矩阵,若有大小 $\ge 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;
}
如果您没有看懂这篇题解,可以在评论区问我,我将会回答您的问题并且修改这篇题解,使它变得更加通俗易懂,服务更多的 $\text{OIer}$。
如果您看懂了这篇题解,可以点个赞,使这篇题解的排名上升,服务更多的 $\text{OIer}$。