话不多说,先贴代码
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; |