1 条题解
-
0
题意简述:
给定一 的矩阵,若有大小 的联通块则同时赋值为空,紧接着整个矩阵同时向下掉落,求最终矩阵的状态。
题目解法:
显而易见,这道题可以分成消除和掉落两个部分。
先看消除怎么消除,由于题目说了连通块能消除当且仅当它的联通块大小 ,所以我们先处理出每个连通块的大小,然后再消除,具体可以用 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; }如果您没有看懂这篇题解,可以在评论区问我,我将会回答您的问题并且修改这篇题解,使它变得更加通俗易懂,服务更多的 。
如果您看懂了这篇题解,可以点个赞,使这篇题解的排名上升,服务更多的 。
- 1
信息
- ID
- 6780
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 94
- 已通过
- 6
- 上传者