话不多说，先贴代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
| #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int map[6][8];
int ans[4][10];
void fall()
{
for (int i = 1; i <= 5; i++)
{
for (int j = 1; j <= 7; j++)
{
int x=i,y=j;
while (map[x][y]!=0&&map[x][y-1]==0&&y>1)
{
map[x][y-1]=map[x][y];
map[x][y]=0; y--;
}
}
}
}
void check()
{
int k = 1;
while (k)
{
int map_D[6][8];
memset(map_D,0,sizeof(map_D));
for (int i = 1; i <= 5; i++)
{
for (int j = 1; j <= 7; j++)
{
if (map[i][j] == 0) break;
if (j>=3&&map[i][j] == map[i][j-1]&&map[i][j-1] == map[i][j-2])
map_D[i][j]=map_D[i][j-1]=map_D[i][j-2]=1;
if (i>=3&&map[i][j] == map[i-1][j]&&map[i-1][j] == map[i-2][j])
map_D[i][j]=map_D[i-1][j]=map_D[i-2][j]=1;
}
}
k=0;
for (int i = 1; i <= 5; i++)
{
for (int j = 1; j <= 7; j++)
{
if (map_D[i][j] == 1)
{
k = 1;
map[i][j] = 0;
map[i][0]--;
}
}
}
if (k) fall();
}
}
void exchange(int x, int y, int k)
{
if (map[x+k][y] != 0)
{
int ex=map[x+k][y];
map[x+k][y] = map[x][y];
map[x][y] = ex;
check();
} else
{
int ex=map[x+k][y];
map[x+k][y] = map[x][y];
map[x][y] = ex;
map[x][0]--; map[x+k][0]++;
fall();
check();
}
}
int boom = 0,n;
void dfs(int x)
{
int sum = 0;
int col[12];
memset(col,0,sizeof(col));
for (int i = 1; i <= 5; i++)
{
sum+=map[i][0];
for (int j = 1; j <= map[i][0]; j++)
col[map[i][j]]++;
}
for(int i = 1; i <= 10; i++)
if(col[i] != 0&&col[i] < 3) return;
if(sum==0&&x<n) return;
if(x==n)
{
if (sum==0)
boom = 1;
return;
}
int map1[6][8];
memcpy(map1,map,sizeof map1);
for (int i = 1; i <= 5; i++)
{
for (int j = 1; j <= map[i][0]; j++)
{
for (int k = 1; k >= -1; k=k-2)
{
if (i == 5 && k == 1) continue;
if (i == 1 && k == -1) continue;
if (map[i][j] == map[i+k][j]) continue;
if (k == -1 && map[i-1][j]!=0) continue;
exchange(i, j, k);
dfs(x+1);
if (boom)
{
ans[1][x] = i-1;
ans[2][x] = j-1;
ans[3][x] = k;
return;
}
memcpy(map,map1,sizeof map);
}
}
}
}
int main(void)
{
int i;
scanf("%d", &n);
for (i = 1; i <= 5; i++)
{
int x_;
map[i][0] = 0;
while (1)
{
scanf("%d", &x_);
if (!x_) break;
map[i][++map[i][0]] = x_;
}
}
dfs(0);
if(boom)
for (i=0;i<n;i++)
printf("%d %d %d\n",ans[1][i],ans[2][i],ans[3][i]);
else printf("-1");
return 0;
} |
写得我心神憔悴，讲道理这题不难，所以难度就只有代码的构建。
对于这种脑残模拟，代码长度成了它报复社会的唯一方法。这题也就照着题目意思分成下面几个步骤
- 深搜：每次对每一个方块进行搜索，分别列举出其向右移和向左移的情况，找出符合题目要求情况即可。
- 下落：对于下落的判断只要是图中一个方块其底下有空，那其就得不断下落，直到接触方块为止，对于下落方块上方的方块也应进行下落。至于执行下落的时间就是在交换后或在去除方块后要执行下落的步骤。
- 去除方块：去除方块就是连续3个相同颜色要进行删除，在此要注意删除是在要搜索完整个图再进行删除，若是搜索到一个可删的三个方块就直接删除的话就无法判断类似“丁”字图形删除的了。同样这个步骤要在交换和下落后进行。
- 注意：去除方块后要执行下落，下落后要执行去除方块。。。直到没有方块去除为止
对于一些剪枝
在每次搜索过程中我们若发现某一颜色少于三种，那这种颜色就永远无法消去，直接return就好了。
1
2
3
4
5
6
7
8
| int col[12];
memset(col,0,sizeof(col));
for (int i = 1; i <= 5; i++)
{
sum+=map[i][0];
for (int j = 1; j <= map[i][0]; j++)
col[map[i][j]]++;
} |
因为题目要求答案按字典序输出，所以如果只是交换的话，和右边的方块交换是没有意义的（因为可看做右边的方块与左边的交换），同样，和相同方块交换也是没有意义的。
1
2
| if (map[i][j] == map[i+k][j]) continue;
if (k == -1 && map[i-1][j]!=0) continue; |