- 2011
T3
- @ 2025-10-2 16:22:13
#include<bits/stdc++.h>
using namespace std;
int n;
int g[5][7], bg[5][5][7];
int cnt[11], bcnt[5][11];
bool st[5][7];
struct Path{
int x, y, d;
}path[5];
void move(int a, int b, int c)
{
swap(g[a][b], g[c][b]);
while(true)
{
bool flag = true;
//处理悬空方格
for(int x = 0; x < 5; x ++)
{
int z = 0;
for(int y = 0; y < 7; y++)
if(g[x][y])
g[x][z ++] = g[x][y];
while(z < 7) g[x][z ++] = 0;
}
memset(st, 0, sizeof st);
for(int x = 0; x < 5; x++)
for(int y = 0; y < 7; y ++)
{
if(g[x][y])
{
int l = x, r = x;
while(l - 1 >= 0 && g[l - 1][y] == g[x][y]) l--;
while(r + 1 < 5 && g[r + 1][y] == g[x][y]) r ++;
if(r - l + 1 >= 3)
{
st[x][y] = true;
flag = false;
}
else
{
l = r = y;
while(l - 1 >= 0 && g[x][l-1] == g[x][y]) l--;
while(r + 1 < 7 && g[x][r+1] == g[x][y]) r ++;
if(r - l + 1 >= 3)
{
st[x][y] = true;
flag = false;
}
}
}
}
if(flag) break;
for(int x = 0; x < 5; x++)
for(int y = 0; y < 7; y++)
if(st[x][y])
{
cnt[0] --;
cnt[g[x][y]] --;
g[x][y] = 0;
}
}
}
bool dfs(int u)
{
if(u == n) return cnt[0] == 0;
for(int i = 1; i <= 10; i++)
if(cnt[i] == 1 || cnt[i] == 2)
return false;
//枚举所有的操作
memcpy(bg[u], g, sizeof g);
memcpy(bcnt[u], cnt, sizeof cnt);
for(int x = 0; x < 5; x ++)
for(int y = 0; y < 7; y++)
{
if(g[x][y])
{
int nx = x + 1;
if(nx < 5)
{
path[u] = {x, y, 1};
move(x, y, nx);
if(dfs(u + 1)) return true;
//恢复现场
memcpy(g, bg[u], sizeof g);
memcpy(cnt, bcnt[u], sizeof cnt);
}
nx = x - 1;
if(nx >= 0 && g[nx][y] == 0)
{
path[u] = {x, y, -1};
move(x, y, nx);
if(dfs(u + 1)) return true;
memcpy(g, bg[u], sizeof g);
memcpy(cnt, bcnt[u], sizeof cnt);
}
}
}
return false;
}
int main()
{
cin >> n;
for(int i = 0; i < 5; i++)
{
int t, j = 0;
while(cin >> t && t)
{
cnt[0] ++; //现在方块的个数
cnt[t] ++;
g[i][j ++] = t;
}
}
if(dfs(0))
{
for(int i = 0; i < n; i++)
cout << path[i].x << " " << path[i].y << " " << path[i].d << endl;
}
else
cout << -1 << endl;
return 0;
}
/*
暴搜
搜索顺序:依次枚举每一步选择哪个方块,以及枚举向左移动还是向右移动
剪枝:
1.把向左移动时如果左侧有方块,则直接剪掉。
2.当某种颜色的方块数量大于0且小于3时,一定无解。
模拟消除:
1.处理悬空
2.处理消除
*/
0 条评论
目前还没有评论...