【NOIP2011】Mayan游戏
本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1312
很考验代码能力的一道搜索模拟题。
首先是大体的思路，显然我们应该把状态定义为某一时刻的棋盘，然后每进行一次操作，就跳到下一个状态，这道题用广搜的话，状态不容易存储，而且要求的步数n很小，所以深搜就可以满足我们的需要。
我们搜索整张棋盘，寻找可以进行的移动，移动后就更新棋盘，该下落的下落，然后判断是否可以消除，消除后再更新，此处应为循环。因为要回溯，所以应保存每步的状态。
关于剪枝，主要有两个，一是遇到相同的不交换；二是仅当左面为空时向左移动，因为，若左面不为空，那么左面的那个之前会向右移动，就导致了重复。
最后注意，根据输出的要求，应该是严格的n步，还有别忘了没有答案输出-1，可值20分呢！
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 5 using namespace std; 6 7 struct Step { 8 int x, y, mov; 9 10 Step(int x = -1, int y = -1, int m = 0) : x(x), y(y), mov(m) {} 11 12 void print() { 13 printf("%d %d %d ", x, y, mov); 14 } 15 } step[10]; 16 17 int n, mt[10][10][10], del[10][10]; //mt第一维中存储走完第i步后的状态 18 19 inline void cop(int d) { 20 for (int i = 0; i < 5; ++i) 21 for (int j = 0; j < 7; ++j) { 22 mt[d][i][j] = mt[d - 1][i][j]; 23 } 24 } 25 26 inline void down(int d) { 27 for (int i = 0; i < 5; ++i) 28 for (int j = 1; j < 7; ++j) 29 if (mt[d][i][j] && !mt[d][i][j - 1]) { 30 int k = j - 1; 31 while (!mt[d][i][k - 1] && k > 0) --k; 32 swap(mt[d][i][j], mt[d][i][k]); 33 } 34 } 35 36 inline int dele(int d) { 37 int flag = 0; 38 for (int i = 0; i < 5; ++i) 39 for (int j = 0; j < 7; ++j) { 40 if (!mt[d][i][j]) continue; 41 if (i - 1 >= 0 && i + 1 < 5 && mt[d][i - 1][j] == mt[d][i][j] && mt[d][i][j] == mt[d][i + 1][j]) del[i - 1][j] = del[i][j] = del[i + 1][j] = flag = 1; 42 if (j - 1 >= 0 && j + 1 < 7 && mt[d][i][j - 1] == mt[d][i][j] && mt[d][i][j] == mt[d][i][j + 1]) del[i][j - 1] = del[i][j] = del[i][j + 1] = flag = 1; 43 } 44 if (!flag) return 0; 45 for (int i = 0; i < 5; ++i) 46 for (int j = 0; j < 7; ++j) 47 if (del[i][j]) mt[d][i][j] = del[i][j] = 0; 48 return 1; 49 } 50 51 inline bool check(int d) { 52 for (int i = 0; i < 5; ++i) 53 for (int j = 0; j < 7; ++j) 54 if (mt[d][i][j]) return false; 55 return true; 56 } 57 58 void dfs(int d) { //该走第d步 59 if (check(d - 1)) { 60 for (int j = 1; j <= n; ++j) 61 step[j].print(); 62 exit(0); 63 } //判断完成 64 if (d == n + 1) return; 65 cop(d); 66 for (int x = 0; x < 5; ++x) 67 for (int y = 0; y < 7; ++y) 68 if (mt[d][x][y]) { 69 if (x + 1 < 5 && mt[d][x][y] != mt[d][x + 1][y]) { 70 step[d] = Step(x, y, 1); 71 swap(mt[d][x][y], mt[d][x + 1][y]); 72 down(d); 73 while (dele(d)) down(d); 74 dfs(d + 1); 75 cop(d); 76 } 77 if (x - 1 >= 0 && !mt[d][x - 1][y]) { 78 step[d] = Step(x, y, -1); 79 swap(mt[d][x][y], mt[d][x - 1][y]); 80 down(d); 81 while (dele(d)) down(d); 82 dfs(d + 1); 83 cop(d); 84 } 85 } 86 } 87 88 int main() { 89 scanf("%d", &n); 90 for (int i = 0; i < 5; ++i) 91 for (int j = 0; !j || mt[0][i][j - 1]; ++j) 92 scanf("%d", &mt[0][i][j]); 93 dfs(1); 94 printf("-1"); 95 return 0; 96 }