记录编号	93553	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]玛雅游戏	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.697 s
提交时间	2014-03-26 21:59:53	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int k;
struct solutions
{
  int x;
  int y;
  int dire;
};
solutions solution[10];
int sumdepth;
bool solved=false;
void solve(int depth,int (*map)[5]);
void swap(int x,int y,int (*map)[5],int dire);
void bomb(int (*map)[5]);
bool empty(int (*map)[5]);
void print();
//====================================
int main()
{
   int map[7][5];
   freopen("mayan.in","r",stdin);
   freopen("mayan.out","w",stdout);
   memset(map,0,sizeof(map));
   cin>>k;
   for(int a=0;a<5;a++)
     solution[a].x=solution[a].y=-1;
   for(int a=0;a<5;a++)
   {
     int b=0;
     int n;
     while (cin>>n&&n)
     {
       map[b][a]=n;
       b++;
     }
   }   
   solve(0,map);
   print();
   //system("pause");
   return 0;
}
//============================================
void solve(int depth,int (*map)[5])
{
   //map[7]
   //map[6]
   //map[5]
   //map[4]
   //map[3]
   //map[2]
   //map[1]
   //map[0]
   if (solved) 
     return;
   if (depth==k)
     return;
   int newmap[7][5];
   for(int x=0;x<5;x++)
     for(int y=0;y<7;y++)
     {
        if (x==1&&y==2&&depth==0)
        {
          int l=1;
        }
        if (x==2&&y==1&&depth==1)
        {
          int l=1;
        }
        if (map[y][x]==0) break;
        if (solved) return;
        if (map[y][x]==map[y][x+1]&&map[y][x-1]!=0) 
          continue;
        if (x!=4&&map[y][x]!=map[y][x+1])
        {
          solution[depth].x=x;
          solution[depth].y=y;
          solution[depth].dire=1;
          memcpy(newmap,map,sizeof(newmap));
          //newmap[6]
          //newmap[5]
          //newmap[4]
          //newmap[3]
          //newmap[2]
          //newmap[1]
          //newmap[0]
         swap(x,y,newmap,1);
          bomb(newmap);
          if (empty(newmap))
          {
            solved=true;
            sumdepth=depth;
            return;
          }
          solve(depth+1,newmap);
        }
        if (solved)
          return;
        if (x!=0&&map[y][x-1]==0)
        {
          solution[depth].x=x;
          solution[depth].y=y;
          solution[depth].dire=-1;
          memcpy(newmap,map,sizeof(newmap));
          swap(x,y,newmap,-1);
          bomb(newmap);
          if (empty(newmap))
          {
            solved=true;
            sumdepth=depth;
            return;
          }
          solve(depth+1,newmap);
        }
     }
}
//=======================================
void swap(int x,int y,int (*map)[5],int dire)
{
   int temp=map[y][x];
   map[y][x]=map[y][x+dire];
   map[y][x+dire]=temp;
   if (map[y][x]==0)
     for(int ny=y+1;ny<7;ny++)
     {
       if (map[ny][x]==0)
       {
         map[ny-1][x]=0;
         break;
       }
       map[ny-1][x]=map[ny][x];
     }
   int nx=x+dire;
   int ny=y-1;
   while (ny!=-1&&map[ny][nx]==0)
   {
     map[ny][nx]=map[ny+1][nx];
     map[ny+1][nx]=0;
     ny--;
   }
}
//======================================
void bomb(int (*map)[5])
{
   //map[5]
   //map[4]
   //map[3]
   //map[2]
   //map[1]
   //map[0]
   bool del[7][5];
   memset(del,false,sizeof(del));
   bool con=false;
   for(int y=0;y<7;y++)
   {
     for(int x=2;x<5;x++)
       if (map[y][x]!=0&&map[y][x]==map[y][x-1]&&map[y][x-1]==map[y][x-2])
       {
         del[y][x]=del[y][x-1]=del[y][x-2]=true;
         con=true;
       }
   }
   for(int x=0;x<5;x++)
     for(int y=2;y<7;y++)
       if (map[y][x]!=0&&map[y][x]==map[y-1][x]&&map[y][x]==map[y-2][x])
       {
         del[y][x]=del[y-1][x]=del[y-2][x]=true;
         con=true;
       }
   if (!con) 
     return;
   for(int x=0;x<5;x++)
     for(int y=0;y<7;y++)
       if (del[y][x])
         map[y][x]=0;
   for(int x=0;x<5;x++)
     for(int y=6;y>=0;y--)
       if (map[y][x]==0)
       {
         for(int ny=y+1;ny<=6;ny++)
         {
            if (map[ny][x]==0)
            {
              map[ny-1][x]=0;
              break;
            }
            map[ny-1][x]=map[ny][x];
         }
         map[6][x]=0;
       }  
   bomb(map);
}
//====================================
bool empty(int (*map)[5])
{
  for(int x=0;x<5;x++)
    for(int y=0;y<7;y++)
      if (map[y][x]!=0)
        return false;
  return true;
}
//====================================
void print()
{
  if (!solved)
  {
    cout<<"-1";
    return;
  }
  for(int a=0;a<=sumdepth;a++)
     printf("%d %d %d\n",solution[a].x,solution[a].y,solution[a].dire);     
}