Mooyo Mooyo

Mooyo Mooyo
题面



题意
就是给你一个 $n\ast 10$n∗10的图，然后找到各个连通块（必须首尾连接的），如果一个连通块中的字符数量不少于K，那么就把这整个连通块全部设为‘0’，如果有两个连通块同时出现字符数量不少于K的，那么我们就可以同时把这两个连通块全部设为0.直达不能再消成0后，就开始降落。使得每一个非0字符下面不再出现‘0’。那么问最后得到的图是什么样？
分析
考察点是dfs+vector，dfs的目的就是找连通块，而vector主要存储中间数据。
我们可以用dfs遍历每一个点，然后找到连通块，具体代码如下

void dfs(int r,int c){
	vis[r][c]=1;   标记
	save[a[r][c]-48].push_back({r,c});    存储属于该联通块的元素
for(int i=0;i<=3;i++){
	int x=r+dir[i][0],y=c+dir[i][1];   四个方向遍历
	if(x<=0||x>n||y<=0||y>10||vis[x][y]||a[x][y]!=a[r][c])   越界以及四个方向要搜索相同的字母
	continue;
	dfs(x,y);  继续深搜
}
return ;
}

除了dfs找连通块，我们还需要clean()函数，来处理

void clean(int num,int v){
	for(int i=0;i<v;i++){
		int nx=save[num][i].x,ny=save[num][i].y;
		a[nx][ny]='0';
	}
}

还需要改图函数

void update(){
	for(int j=1;j<=10;j++){
		for(int i=1;i<=n;i++){
			if(a[i][j]=='0') continue;
			ce.push_back(a[i][j]);
		}
		int v=ce.size(),q;///n-v个0
		for(q=1;q<=n-v;q++)
			a[q][j]='0';
		for(int nu=0;nu<v;nu++,q++)
			a[q][j]=ce[nu];
		ce.clear();
	}
}

AC代码

///dfs找到连通块 clean清除符合要求的连通块 update 更新连通块
#include <bits/stdc++.h>
using namespace std;
int n,k,vis[105][15];
char a[105][15];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
typedef struct{
int x;
int y;
}P;
vector<P>save[10];
vector<char>ce;
void dfs(int r,int c){
	vis[r][c]=1;
	save[a[r][c]-48].push_back({r,c});
for(int i=0;i<=3;i++){
	int x=r+dir[i][0],y=c+dir[i][1];
	if(x<=0||x>n||y<=0||y>10||vis[x][y]||a[x][y]!=a[r][c])
	continue;
	dfs(x,y);
}
return ;
}
void clean(int num,int v){
	for(int i=0;i<v;i++){
		int nx=save[num][i].x,ny=save[num][i].y;
		a[nx][ny]='0';
	}
}
void update(){
	for(int j=1;j<=10;j++){
		for(int i=1;i<=n;i++){
			if(a[i][j]=='0') continue;
			ce.push_back(a[i][j]);
		}
		int v=ce.size(),q;///n-v个0
		for(q=1;q<=n-v;q++)
			a[q][j]='0';
		for(int nu=0;nu<v;nu++,q++)
			a[q][j]=ce[nu];
		ce.clear();
	}
}
int main(){
	bool success=true;
	int i,j,flag;
	cin>>n>>k;
	for(i=1;i<=n;i++){
		for(j=1;j<=10;j++){
			cin>>a[i][j];
		}
	}///输完图
	while(1){
	for(i=1;i<=n;i++){
		for(j=1;j<=10;j++){
			if(a[i][j]=='0'||vis[i][j]) continue;
			dfs(i,j);
				flag=a[i][j]-48;
			int v=save[a[i][j]-48].size();
		if(v>=k){
				/*printf("%d有%d个\n",a[i][j]-48,save[a[i][j]-48].size());*/
				clean(a[i][j]-48,v);
				success=false;
				/*printf("***************\n"); for(int q=1;q<=n;q++){ for(int t=1;t<=10;t++){ cout<<a[q][t]; } putchar('\n'); }*/
		}
			save[flag].clear();
			/*printf("%d被消了%d个\n",flag,v);*/
		}
	}
		/*printf("123\n");*/
		if(success) break;
		success=true;
		update();
		memset(vis,0,sizeof(vis));
		/*for(int q=1;q<=n;q++){ for(int t=1;t<=10;t++){ cout<<a[q][t]; } putchar('\n'); }*/
	///消消乐
	/* */
	}
	for(int q=1;q<=n;q++){
		for(int t=1;t<=10;t++){
			cout<<a[q][t];
	}
		putchar('\n');
		}
	return 0;
}