http://codeforces.com/group/NVaJtLaLjS/contest/238203/problem/C
题意：
输入数字K和一副纯数字字符画，相同数字构成四连通。假如这个四连通大小大于K，清除为0。然后其他数字会因重力掉落到最底端。重复该过程，输出最终图案。
如：（K=4）
335450 335450 000050 000050 000000 113350 => 003350 => 005450 => 005450 => 000050 111133 000033 333333 000000 005450
输入输出：输入行数N和消除数K，输入N行字符画。每行固定10个数字（0~9）。1≤N≤100，K1≤K≤10N。
示例：
Input：
6 3 0000000000 0000000300 0054000300 1054502230 2211122220 1111111223
Output：
0000000000 0000000000 0000000000 0000000000 1054000000 2254500000
本来是用DFS/BFS求连通块的简单题目，这里加了两个让萌新懵逼的条件：一个超量消除，一个重力下落。
关于DFS/BFS，请见下列题解：
https://www.cnblogs.com/Kaidora/p/10392641.html
https://www.cnblogs.com/Kaidora/p/10392293.html
重力是很好解决的。对于一列字符，弄两个变量i，k，从下往上扫描共N次循环，i++停留在0处，k++直至k>N。
循环每次都交换字符[k]与字符[i]。因为这里只有0与非0，非0要么与自己交换，要么与最低的0交换。
重复10次就可以搞定。
建议先写好重力，然后自己输入测试，看看重力处理是否正确，再写其他部分。
另一个是消除。这个有点坑。蒟蒻写的递归DFS出现了没有全部消除的bug。
举个栗子：（K=3）
100
111
蒟蒻是怎么计数的？用返回值表明子分支有多少节点，或者用全局变量来统计数到第几个。结果出现了这样的沙雕过程：
左下角的第一个，左上第二个，返回；
中间第三个，右边第四个，消除返回，消除返回；
消除返回。
然后第二个1在重力处理中就掉下来了。输出过程蒟蒻看得一脸懵逼。
不管是BFS还是DFS，扫描到这种孤儿时因为不满K值就退出，会造成满K值消除时被漏掉。
所以搜索一个连通块时要把所有字符坐标都记下来，满足K值时就可以全部消除。至少蒟蒻是想不出要怎么在DFS/BFS函数里实现这个功能。
这里可以用队列，不过本题最多100*10个字符，可以用数组代替队列。对于BFS，使用数组比使用队列容易。
只需用两个变量f，b表示队列首尾，以此为下标就可以存取数组元素。这样不需要pop()就可以访问下一个元素，而不用再用另一个队列来保存字符坐标。
清空数组直接用memset()，不用循环pop()。
（注意！数组大小是死的。这种操作只能用于队列总吞吐量小于数组大小的时候。比如这里这个队列长度不可能大于1000）
现在只剩两个问题，一个如何避免重复找连通块，一个如何结束这个循环。
避免重复：维护另一张相同大小的地图scanned。搜索过字符map[x][y]就把scanned[x][y]记为1。之后就可以跳过这个字符。
结束循环：记下最大的连通块大小。大于等于K就执行消除、重力、重复；小于K就输出。
代码如下：
（这里我的重力实现比较难看，不像我解释的那样好懂。）
（另外，我这里的最底端在数组中是map[1]。第一行从最底端开始，往上数。除了输入输出平时用for和数组都从1开始，更符合平时写循环条件的习惯。）
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 5 char map[102][12]={0}; 6 char scanned[102][12]={0}; 7 char queue[1001][2]={0}; 8 int N=0,K=0; 9 int dx[4]={-1,+1,0,0}; 10 int dy[4]={0,0,-1,+1}; 11 12 int dfs(int x,int y,int count) 13 { 14 count++; 15 queue[count][0]=x,queue[count][1]=y; 16 scanned[x][y]=1; 17 for(int i=0;i<4;i++) 18 { 19 if( scanned[x+dx[i]][y+dy[i]]==0 ) 20 if( map[x][y]==map[x+dx[i]][y+dy[i]] ) 21 { 22 count=dfs(x+dx[i],y+dy[i],count); 23 } 24 } 25 // if(count>=K)map[x][y]=‘0‘; 26 return count; 27 } 28 29 int cleanqueue() 30 { 31 for(int i=1;queue[i][0];i++) 32 { 33 map[ (int)queue[i][0] ][ (int)queue[i][1] ]=‘0‘; 34 } 35 } 36 37 int main() 38 { 39 scanf("%d%d",&N,&K); getchar(); 40 for(int n=N;n>0;n--) 41 { 42 gets(&map[n][1]); 43 } 44 45 int last,tmp; 46 47 Start:; 48 memset(scanned,0,102*12*sizeof(char)); 49 last=tmp=0; 50 51 for(int x=1;x<=N;x++) 52 { 53 for(int y=1;y<=10;y++) 54 { 55 if(scanned[x][y]==0 && map[x][y]!=‘0‘) 56 { 57 tmp=dfs(x,y,0); 58 if(tmp>=K)cleanqueue(); 59 memset(queue,0,2002*sizeof(char)); 60 if(tmp>last)last=tmp; 61 } 62 } 63 } 64 /* 65 //debug 66 puts(""); 67 for(int n=N;n>0;n--) 68 puts(&map[n][1]); 69 */ 70 if(last>=K) 71 { 72 73 for(int y=1;y<=10;y++) 74 { 75 tmp=1; 76 for(int x=1;x<=N;x++) 77 { 78 if(map[x][y]!=‘0‘) 79 { 80 if(x!=tmp) 81 { 82 map[tmp][y]=map[x][y]; 83 map[x][y]=‘0‘; 84 } 85 tmp++; 86 } 87 } 88 } 89 } 90 /* 91 //debug 92 puts(""); 93 for(int n=N;n>0;n--) 94 puts(&map[n][1]); 95 */ 96 97 if(last>=K)goto Start; 98 99 //print 100 101 for(int n=N;n>0;n--) 102 puts(&map[n][1]); 103 104 105 return 0; 106 }
原文：https://www.cnblogs.com/Kaidora/p/10416124.html