题解 P1312 【Mayan游戏】

· · 题解 

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10;
int step;
int f[maxn][maxn],b[maxn][maxn][maxn],g[maxn][maxn];
/*
    int f[6][3],b[6][6][8],g[6][8];
    ！！！错误示范
         开数组不要吝啬，否则很容易错 
*/
//f数组表示答案每一步的情况，例如f[2][0],f[2][1]表示要移动的位置的横纵坐标，f[2][2]表示向左移（-1）或向右移（1）
//b数组表示第几步时的情况，例如b[3][i][j]表示移动了3步时第i列第j行的数字是几 
void update(int k)
{
     bool flag=true;
     while(flag)
     {
       flag=false;
       for(int i=1;i<=5;i++)
       {
         int p=1;
         for(int j=1;j<=7;j++)
           if(b[k][i][j])
             b[k][i][p++]=b[k][i][j];
         while(p<=7)
           b[k][i][p++]=0; // 抹掉该列上面的数据； 
       }
       /* 
            法一 
       for(int j=1;j<=7;j++)
         for(int i=1;i+2<=5;i++)
         {
           if(!b[k][i][j])
             continue;
           if(b[k][i][j]==b[k][i+1][j] && b[k][i][j]==b[k][i+2][j])
             flag=g[i][j]=g[i+1][j]=g[i+2][j]=true;
         }
       for(int i=1;i<=5;i++)
         for(int j=1;j+2<=7;j++)
         {
           if(!b[k][i][j])
             break;
           if(b[k][i][j]==b[k][i][j+1] && b[k][i][j]==b[k][i][j+2])
             flag=g[i][j]=g[i][j+1]=g[i][j+2]=true;
         }
       */
       //      法二 
       for(int i=1;i<=5;i++)
         for(int j=1;j<=7;j++)
         {
           if(!b[k][i][j])
             break; // 由于已经“落”过了，所以如果没有数据就跳出 
           if(i<=3 && b[k][i][j]==b[k][i+1][j] && b[k][i][j]==b[k][i+2][j]) //判断横向的合并情况； 
             flag=g[i][j]=g[i+1][j]=g[i+2][j]=true;  // 设置标志 
           if(j<=5 && b[k][i][j]==b[k][i][j+1] && b[k][i][j]==b[k][i][j+2]) //判断纵向的合并情况； 
             flag=g[i][j]=g[i][j+1]=g[i][j+2]=true;
         }
       for(int i=1;i<=5;i++)
         for(int j=1;j<=7;j++)
           if(g[i][j])
             b[k][i][j]=g[i][j]=0;
     }
}
bool dfs(int k)
{
     for(int i=1;i<=5;i++)
       for(int j=1;j<=7;j++)
         b[k][i][j]=b[k-1][i][j];
     //将第i步的情况先复制为上一步向下深搜一次的情况 
     update(k);//按照规则进行消除方块 
     if(k>step)
     {
       //主程序里从第一步开始搜，如果搜了step+1次，就不要继续了 
       for(int i=1;i<=5;i++)
         if(b[k][i][1])
           return false;
       //如果有某一列没有清除干净，说明不能消除干净 
       return true;
     }
     for(int i=1;i<=5;i++)
       for(int j=1;j<=7;j++)
         if(b[k][i][j])//如果当前位置有颜色(因为操作必须对有方块的位置操作)
         { 
           if(i<5 && b[k][i][j]!=b[k][i+1][j])
           {
             swap(b[k][i][j],b[k][i+1][j]);
             f[k][0]=i;
             f[k][1]=j;
             f[k][2]=1;
             if(dfs(k+1))
               return true;
             //如果这样操作一次后下一次深搜刚好消除了所有方块，就return true;
             //但不能直接return dfs(k+1); 
             //因为即使这次操作不成功，并不代表以后没机会成功 
             swap(b[k][i][j],b[k][i+1][j]);
           }
           /*
             因为题目要求操作1优先于操作-1
             所以只要既能操作1又能操作-1得到的情况我们就用操作1来完成
             而题目有让字典序输出答案，我们正好是按照i从小到大来深搜
             所以所有能-1操作的，比如4 5 -1
             我们都会在它之前先枚举  3 5 1，所以就不用大范围搜索-1的操作了
             除了一种特殊情况： 
               当某一个方块左边是空时，这种情况在上面无法用1操作完成 

           */
           if(i>1 && !b[k][i-1][j])
           {
             swap(b[k][i][j],b[k][i-1][j]);
             f[k][0]=i;
             f[k][1]=j;
             f[k][2]=-1;
             if(dfs(k+1))
               return true;
             swap(b[k][i][j],b[k][i-1][j]);
           }
         }
     return false; 
}
int main()
{
    scanf("%d",&step);
    for(int i=1;i<=5;i++)
    {
      int x,j=1;
      scanf("%d",&x);
      while(x)
      {
        b[0][i][j++]=x;
        scanf("%d",&x);
      }
    }
    bool flag=dfs(1);
    if(flag)
    {
      for(int i=1;i<=step;i++)
        printf("%d %d %d\n",f[i][0]-1,f[i][1]-1,f[i][2]);
        //注意题目说坐标从0开始所以把横纵坐标减1 
    }
    else
      printf("-1\n");
    system("pause");
    return 0;
}