原题
Problem C. Mooyo Mooyo
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 256 megabytes
With plenty of free time on their hands (or rather, hooves), the cows on Farmer John’s farm often pass the time by playing video games. One of their favorites is based on a popular human video game called Puyo Puyo; the cow version is of course called Mooyo Mooyo. The game of Mooyo Mooyo is played on a tall narrow grid N cells tall (1 ≤ N ≤ 100) and 10 cells wide. Here is an example with N = 6:
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223
Each cell is either empty (indicated by a 0), or a haybale in one of nine different colors (indicated by characters 1..9). Gravity causes haybales to fall downward, so there is never a 0 cell below a haybale.
Two cells belong to the same connected region if they are directly adjacent either horizontally or vertically, and they have the same nonzero color. Any time a connected region exists with at least K cells, its haybales all disappear, turning into zeros. If multiple such connected regions exist at the same time, they all disappear simultaneously. Afterwards, gravity might cause haybales to fall downward to fill some of the resulting cells that became zeros. In the resulting configuration, there may again be connected regions of size at least K cells. If so, they also disappear (simultaneously, if there are multiple such regions), then gravity pulls the remaining cells downward, and the process repeats until no connected regions of size at least K exist.
Given the state of a Mooyo Mooyo board, please output a final picture of the board after these operations have occurred.
Input
The first line of input contains N and K(1 ≤ K ≤ 10N). The remaining N lines specify the initial state of the board.
Output
Please output N lines, describing a picture of the final board state.
Example
input
6 3
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223
Output
0000000000
0000000000
0000000000
0000000000
1054000000
2254500000
Note
In the example above, if K=3, then there is a connected region of size at least K with color 1 and also one with color 2. Once these are simultaneously removed, the board temporarily looks like this:
0000000000
0000000300
0054000300
1054500030
2200000000
0000000003
Then, gravity takes effect and the haybales drop to this configuration:
0000000000
0000000000
0000000000
0000000000
1054000300
2254500333
Again, there is a region of size at least K (with color 3). Removing it yields the final board configuration:
0000000000
0000000000
0000000000
0000000000
1054000000
2254500000
题目大意
这道题是讲给一个图,然后图里面数字的大小为这个物品的颜色种类,数字为0代表该位置是空的,相邻的同色物品可以构成连通块.题目有给一个k,让你检查这个图里每个连通块的大小,如果大于等于k则把这个连通块消除(使该连通块里的所有物品的颜色种类均为0),消除之后剩余的物品还会随重力下落,如此重复直至图不存在连通块大小大于等于k,再输出这个图.
题目解析
用一个char的二维数组存题目给出的图,然后扫一遍图,如果检测到不为0的位置就dfs一次.dfs要用一个变量来记录dfs的步数,用来判定是否需要消除.dfs扫过的点也要用一个队列存起来,如果步数大于等于k,则把存起来的点全都赋值为0,否则清空队列.接着再写一个重力函数来更新重力作用后的图,如此重复知道图不能更新为止,再输出该图.关于重力函数的实现方法有多种,这里我感觉我写得很丑,仅供参考.
代码
1 #include <cstdio>
2 #include <cmath>
3 #include <iostream>
4 #include <cstring>
5 #include <algorithm>
6 #include <vector>
7 #include <string>
8 #include <utility>
9 #include <queue>
10 #include <stack>
11 const int INF=0x3f3f3f3f;
12 using namespace std;
13
14 typedef pair<int,int> P;
15 int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; //dfs前进方向
16 char map[100][10]; //存图
17 int scan[100][10]; //标记dfs走过的位置(没走过为0,走过为1)
18 int n,k;
19 queue<P> que; //存dfs走过的点
20
21 void clear(queue<P>& q) //清空队列
22 {
23 queue<P> empty;
24 swap(empty,q);
25 }
26
27 int dfs(int x,int y,int c) //c用来记录步数
28 {
29 scan[x][y]=1;
30 que.push(P(x,y));
31 c++;
32 for(int i=0;i<4;i++)
33 {
34
35 int nx,ny;
36 nx=x+dx[i],ny=y+dy[i];
37 if(nx>=0&&nx<n&&ny>=0&&ny<10&&!scan[nx][ny]&&(map[nx][ny]==map[x][y])) c=dfs(nx,ny,c);
38 }
39 return c;
40 }
41
42 void update() //重力函数
43 {
44 int t;
45 for(int j=0;j<10;j++) //从第一列底部开始往上更新
46 {
47 t=0;
48 for(int i=n-1;i>=0;i--)
49 {
50 if(map[i][j]=='0') t++;
51 else
52 {
53
54 if(t)
55 {
56 while(i>=0&&map[i][j]!='0') map[i+t][j]=map[i][j],map[i][j]='0',i--;
57 i=i+t+1,t=0;
58
59 }
60 }
61 }
62 }
63
64 }
65
66 int main()
67 {
68 int c,s; //s用来记录图有没有被更新过
69 cin>>n>>k;
70 getchar();
71 for(int i=0;i<n;i++)
72 {
73 for(int j=0;j<10;j++)
74 scanf("%c",&map[i][j]);
75 getchar();
76 }
77 while(1) //如果不能更新了会跳出该循环
78 {
79 s=0;
80 for(int i=0;i<n;i++)
81 for(int j=0;j<10;j++)
82 if(map[i][j]!='0')
83 {
84 c=dfs(i,j,0);
85
86 if(c>=k)
87 {
88 while(que.size())
89 {
90 P p=que.front();que.pop();
91 map[p.first][p.second]='0';
92 }
93 s++;
94 }
95 else clear(que);
96 }
97 if(!s) break;
98 update();
99 memset(scan,0,sizeof(scan)); //每次更新过后,不要忘记初始化
100 }
101
102 for(int i=0;i<n;i++)
103 {
104 for(int j=0;j<10;j++)
105 cout<<map[i][j];
106 cout<<endl;
107 }
108 return 0;
109 }