题解 P1312 【Mayan游戏】
P1312 Mayan游戏
很显然，这一题数据范围很小，是个搜索题。再看是个游戏，可能要用到简单的模拟来模拟每一步的移动。
于是大方向就有了：
深搜 + 模拟 ！
常量定义：
#define SIZE 10 //n值范围
#define LINE 5 //行（因为输入数据中x、y翻转了）
#define ROW 7 //列
#define LNG 3 //消除所满足的最小长度首先，为了方便操作，我们定义一个 类：
class Mayan
{
private:
int board[LINE][ROW]; //游戏棋盘
bool flag[LINE][ROW]; //标记数组，消除方块时用到
...
public:
...
};然后，我们考虑游戏过程中的过程(写在类中)：
-
初始化
void initialize() //读入初始棋盘 { memset(board, 0, sizeof(board)); for (register int i = 0; i < LINE; i++) { for (register int j = 0; ; j++) { scanf("%d", &board[i][j]); if (board[i][j] == 0) break; } } } -
获得某一位置上的颜色
int color(int x, int y) { return board[x][y]; } -
更新棋盘
void fall(int x, int y) //方块下落 { int ny = y - 1; while (ny >= 0 && board[x][ny] == 0) ny--; ny++; swap(board[x][ny], board[x][y]); } void update() { for (register int i = 0; i < LINE; i++) { for (register int j = 1; j < ROW; j++) //最底部的方块不用考虑下落 { if (board[i][j] != 0) fall(i, j); } } } -
检查是否有方块可以清除
bool check() { bool rv = false; memset(flag, false, sizeof(flag)); for (register int x = 0; x < LINE; x++) { for (register int y = 0; y < ROW; y++) { if (board[x][y] == 0) continue; int e1, e2; //端点 int og = board[x][y]; //original color //水平方向 e1 = e2 = x; while (e1 >= 0 && board[e1][y] == og) e1--; e1++; while (e2 < LINE && board[e2][y] == og) e2++; e2--; if (e2 - e1 + 1 >= LNG) //length >= 3 { rv = true; //有方块可以清除 for (register int i = e1; i <= e2; i++) flag[i][y] = true; } //竖直方向 e1 = e2 = y; //e1 below e2 while (e1 >= 0 && board[x][e1] == og) e1--; e1++; while (e2 < ROW && board[x][e2] == og) e2++; e2--; if (e2 - e1 + 1 >= LNG) //length >= 3 { rv = true; for (register int i = e1; i <= e2; i++) flag[x][i] = true; } } } return rv; } void clear() { for (register int i = 0; i < LINE; i++) { for (register int j = 0; j < ROW; j++) { if (flag[i][j]) board[i][j] = 0; } } update(); //让悬空方块下落 } -
移动方块
void move(int x, int y, int g) //g为移动方向，g = 1向右移，g = -1向左移 { //default can move swap(board[x][y], board[x+g][y]); update(); while (check()) clear(); } -
判断游戏是否结束
bool empty() { for (register int i = 0, j = 0; i < LINE; i++) { if (board[i][j] != 0) return false; } return true; } -
运算符重载(辅助)
因为涉及到回溯与赋值，重载运算符会让其更加便捷
Mayan operator=(const Mayan& m) { for (register int i = 0; i < LINE; i++) { for (register int j = 0; j < ROW; j++) { this -> board[i][j] = m.board[i][j]; this -> flag[i][j] = m.flag[i][j]; } } return *this; };接下来，就是搜索了：
由于状态太多，广搜储存内存太大，所以这里使用深搜。
其实这道题有很多可以剪枝的地方，但是好像不需要剪那么多，这里我只用几个基本的剪枝。
- 相同颜色不交换;
- 方块只往右移(左移可以被左边方块右移替换)。
于是，我们可以写出如下函数：
void dfs(int step) { if (step > n) { if (mayan.empty()) { answer(); //输出结果 exit(0); //直接退出 } return ; //规定步结束后，游戏没有结束，无解 } for (register int i = 0; i < LINE - 1; i++) //only move to right { for (register int j = 0; j < ROW; j++) { if (mayan.color(i, j) == mayan.color(i + 1, j)) //相同颜色不交换 continue; ans[step][1] = j; if (mayan.color(i, j) == 0) //空方块右移即右边的有色方块左移 { ans[step][0] = i + 1; ans[step][2] = -1; } else { ans[step][0] = i; ans[step][2] = 1; } Mayan temp = mayan; mayan.move(i, j, 1); dfs(step+1); mayan = temp; //回溯 } } }最后，
大功告成！
#include <cstdio> #include <cstring> #include <cstdlib> //exit() #include <algorithm> #define SIZE 10 #define LINE 5 #define ROW 7 #define LNG 3 using namespace std; class Mayan { private: int board[LINE][ROW]; bool flag[LINE][ROW]; void fall(int x, int y) { int ny = y - 1; while (ny >= 0 && board[x][ny] == 0) ny--; ny++; swap(board[x][ny], board[x][y]); } void update() { for (register int i = 0; i < LINE; i++) { for (register int j = 1; j < ROW; j++) //brick on the bottom can't fall { if (board[i][j] != 0) fall(i, j); } } } bool check() { bool rv = false; memset(flag, false, sizeof(flag)); for (register int x = 0; x < LINE; x++) { for (register int y = 0; y < ROW; y++) { if (board[x][y] == 0) continue; int e1, e2; //endpoint int og = board[x][y]; //original color //horizontal e1 = e2 = x; while (e1 >= 0 && board[e1][y] == og) e1--; e1++; while (e2 < LINE && board[e2][y] == og) e2++; e2--; if (e2 - e1 + 1 >= LNG) //length >= 3 { rv = true; for (register int i = e1; i <= e2; i++) flag[i][y] = true; } //vertical e1 = e2 = y; //e1 below e2 while (e1 >= 0 && board[x][e1] == og) e1--; e1++; while (e2 < ROW && board[x][e2] == og) e2++; e2--; if (e2 - e1 + 1 >= LNG) //length >= 3 { rv = true; for (register int i = e1; i <= e2; i++) flag[x][i] = true; } } } return rv; } void clear() { for (register int i = 0; i < LINE; i++) { for (register int j = 0; j < ROW; j++) { if (flag[i][j]) board[i][j] = 0; } } update(); } public: void initialize() { memset(board, 0, sizeof(board)); for (register int i = 0; i < LINE; i++) { for (register int j = 0; ; j++) { scanf("%d", &board[i][j]); if (board[i][j] == 0) break; } } } int color(int x, int y) { return board[x][y]; } void move(int x, int y, int g) //g is the direction, g = 1 || -1 { //default can move swap(board[x][y], board[x+g][y]); update(); while (check()) clear(); } bool empty() { for (register int i = 0, j = 0; i < LINE; i++) { if (board[i][j] != 0) return false; } return true; } Mayan operator=(const Mayan& m) { for (register int i = 0; i < LINE; i++) { for (register int j = 0; j < ROW; j++) { this -> board[i][j] = m.board[i][j]; this -> flag[i][j] = m.flag[i][j]; } } return *this; }; }; Mayan mayan; int ans[SIZE][3]; int n; void dfs(int step); inline void answer(); int main() { scanf("%d", &n); mayan.initialize(); dfs(1); printf("-1\n"); //无解dfs()正常退出 return 0; } void dfs(int step) { if (step > n) { if (mayan.empty()) { answer(); exit(0); } return ; } for (register int i = 0; i < LINE - 1; i++) //only move to right { for (register int j = 0; j < ROW; j++) { if (mayan.color(i, j) == mayan.color(i + 1, j)) continue; ans[step][1] = j; if (mayan.color(i, j) == 0) //current is 0 { ans[step][0] = i + 1; ans[step][2] = -1; } else { ans[step][0] = i; ans[step][2] = 1; } Mayan temp = mayan; mayan.move(i, j, 1); dfs(step+1); mayan = temp; } } } inline void answer() { for (register int i = 1; i <= n; i++) { for (register int j = 0; j < 3; j++) printf("%d ", ans[i][j]); putchar('\n'); } }