Luogu 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:
    ...
};

然后，我们考虑游戏过程中的过程(写在类中)：

1. 初始化

    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;
            }
        }
    }

2. 获得某一位置上的颜色

    int color(int x, int y)
    {
        return board[x][y];
    }

3. 更新棋盘

    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);
            }
        }
    }

4. 检查是否有方块可以清除

    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();    //让悬空方块下落
    }

5. 移动方块

    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();
    }

6. 判断游戏是否结束

    bool empty()
    {
        for (register int i = 0, j = 0; i < LINE; i++)
        {
            if (board[i][j] != 0)
                return false;
        }
        return true;
    }

7. 运算符重载(辅助)

   因为涉及到回溯与赋值，重载运算符会让其更加便捷

    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;
    };

   接下来，就是搜索了：

   由于状态太多，广搜储存内存太大，所以这里使用深搜。

   其实这道题有很多可以剪枝的地方，但是好像不需要剪那么多，这里我只用几个基本的剪枝。

   1. 相同颜色不交换;

   2. 方块只往右移(左移可以被左边方块右移替换)。

      于是，我们可以写出如下函数：

      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');
      }
      }