P1312 Mayan游戏
这道题跟斗地主都是大模拟啊！稍微挂一点可能就爆零了！
图肯定能存，直接二维数组扔进去即可。
然后套dfs模板，搜索就先照那样搜。
核心操作有两个：一个是判断那些块可以消掉，一个是把那些可以消的消了。
第一个操作的核心代码是这样的：
for(int i = 1; i <= 5; i++) { for(int j = 1; j <= 7; j++) { if(G[i][j] && i - 1 >= 1 && i + 1 <= 5 && G[i][j] == G[i + 1][j] && G[i][j] == G[i - 1][j]) { flag = true; vis[i][j] = vis[i - 1][j] = vis[i + 1][j] = true; for(int k = i - 2; k >= 1; k--) { if(G[i][j] == G[k][j]) vis[k][j] = true; else break; } for(int k = i + 2; k <= 5; k++) { if(G[i][j] == G[k][j]) vis[k][j] = true; else break; } } if(G[i][j] && j - 1 >= 1 && j + 1 <= 7 && G[i][j] == G[i][j - 1] && G[i][j] == G[i][j + 1]) { flag = true; vis[i][j] = vis[i][j - 1] = vis[i][j + 1] = true; for(int k = j - 2; k >= 1; k--) { if(G[i][j] == G[i][k]) vis[i][k] = true; else break; } for(int k = j + 2; k <= 7; k++) { if(G[i][j] == G[i][k]) vis[i][k] = true; else break; } } }} 个人认为没办法用dfs去找可以消的块，于是就用了这种暴力操作。
第二个操作比较麻烦，稍微写错就爆零了。。。
正确的解决思路是把可以消的点先全部弄掉，变成一副悬空的状态。
之后再遍历每一列，再从下往上遍历，记录当前遇到了几个空气，直接替换，原位置变成空气即可。
还有一点难发现的：当新状态出来之后，必须先掉下来，再判断能否消除。
然后两个部分就没什么问题了。
但是这样会TLE。我们需要剪枝！
- 交换相同方块时，剪枝！
- 一个方块向左交换时，如果左边有方块，剪枝！这时让那个方块向右交换更优。
代码：
/************************************************************************* @Author: Garen @Created Time : Wed 30 Jan 2019 12:53:57 PM CST @File Name: P1312.cpp @Description: ************************************************************************/#includeusing std::cin;using std::cout;using std::endl;const int maxn = 6, maxm = 8;int G[maxn][maxm];int backup[maxn][maxn][maxm];struct Nodes { int x, y, g; Nodes(int x, int y, int g): x(x), y(y), g(g) {}};std::vector answers;bool vis[maxn][maxm];int n;void copy_one(int t) { for(int i = 1; i <= 5; i++) for(int j = 1; j <= 7; j++) backup[t][i][j] = G[i][j];}void copy_two(int t) { for(int i = 1; i <= 5; i++) for(int j = 1; j <= 7; j++) G[i][j] = backup[t][i][j];}bool find() { bool flag = false; for(int i = 1; i <= 5; i++) { for(int j = 1; j <= 7; j++) { if(G[i][j] && i - 1 >= 1 && i + 1 <= 5 && G[i][j] == G[i + 1][j] && G[i][j] == G[i - 1][j]) { flag = true; vis[i][j] = vis[i - 1][j] = vis[i + 1][j] = true; for(int k = i - 2; k >= 1; k--) { if(G[i][j] == G[k][j]) vis[k][j] = true; else break; } for(int k = i + 2; k <= 5; k++) { if(G[i][j] == G[k][j]) vis[k][j] = true; else break; } } if(G[i][j] && j - 1 >= 1 && j + 1 <= 7 && G[i][j] == G[i][j - 1] && G[i][j] == G[i][j + 1]) { flag = true; vis[i][j] = vis[i][j - 1] = vis[i][j + 1] = true; for(int k = j - 2; k >= 1; k--) { if(G[i][j] == G[i][k]) vis[i][k] = true; else break; } for(int k = j + 2; k <= 7; k++) { if(G[i][j] == G[i][k]) vis[i][k] = true; else break; } } } } if(!flag) return false; for(int i = 1; i <= 5; i++) { for(int j = 1; j <= 7; j++) { if(vis[i][j]) { vis[i][j] = G[i][j] = 0; } } } return true;}void update() { for(int i = 1; i <= 5; i++) { int now = 0; for(int j = 1; j <= 7; j++) { if(!G[i][j]) now++; else { if(!now) continue; G[i][j - now] = G[i][j]; G[i][j] = 0; } } }}bool empty() { for(int i = 1; i <= 5; i++) if(G[i][1]) return false; return true;}void dfs(int t) { if(t == n) { if(empty()) { for(auto it : answers) cout << it.x << ' ' << it.y << ' ' << it.g << endl; exit(0); } return; } copy_one(t); for(int i = 1; i <= 5; i++) { for(int j = 1; j <= 7; j++) { if(G[i][j]) { // right if(i + 1 <= 5 && G[i][j] != G[i + 1][j]) { std::swap(G[i][j], G[i + 1][j]); answers.push_back(Nodes(i - 1, j - 1, 1)); update(); while(find()) update(); dfs(t + 1); copy_two(t); answers.pop_back(); } // left if(i - 1 >= 1 && G[i - 1][j] == 0) { std::swap(G[i][j], G[i - 1][j]); answers.push_back(Nodes(i - 1, j - 1, -1)); update(); while(find()) update(); dfs(t + 1); copy_two(t); answers.pop_back(); } } } }}int main() { cin >> n; for(int i = 1; i <= 5; i++) { int temp; for(int j = 1; ; j++) { cin >> temp; if(temp) G[i][j] = temp; else break; } } dfs(0); cout << -1 << endl; return 0;}