NOIP 2011 Mayan游戏

首先说明一下，有解的意思是恰好N步可以出解，小于N步的不算。

这道题是一个典型的搜索题，思路不难，也不需要太多剪枝，主要考察的是选手对编程语言的熟练程度，细心程度和调试能力。

唯一的剪枝就是对于某个方块，只要考虑往右移的情况就可以了，只有当它的左边是空的才考虑左移。

由于DFS时需要传递大量数据，因此添加一个类似栈的结构，这样DSF时只要传递深度就可以了。此外，由于使用了结构体，因此传递给函数的时候没有特殊情况最好使用指针，不然程序会复制一份，造成效率降低。

drop函数用于使方块下落。work函数用于消除方块。

程序中还使用了一个剪枝：不交换相同颜色的方块。这个剪枝可以缩短一半的运行时间，不过本人认为这个剪枝不太符合题意。

代码如下

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define W 5
#define H 7

typedef struct node
{
   short v[W][H];
}node;

short map[W][H];
int N,totcolor;
node S[7];
int op[7][3];

void ptmap(node *a)   //for debug
{
   int i,j;
   for(i = 0;i < W;i ++)
   {
       for(j = 0;j < H;j ++)    fprintf(stderr,"%d",a->v[i][j]);
       fprintf(stderr,"\n");
   }
   fprintf(stderr,"\n");
}

inline int poss(node *a)    //unnecessay check
{
   int i,j,cnt[10];
   memset(cnt,0,sizeof(cnt));
   for(i = 0;i < W;i ++)
       for(j = 0;j < H;j ++)
           cnt[a->v[i][j]] ++;
   for(i = 1;i <= totcolor;i ++)
       if(cnt[i] == 1 || cnt[i] == 2)    return 0;
   return 1;
}

void init()
{
   scanf("%d\n",&N);
   int i,j,t;
   for(i = 0;i < W;i ++)
       for(j = 0;;j ++)
       {
           scanf("%d",&t);
           if(t == 0)    break;
           if(t > totcolor)    totcolor = t;
           map[i][j] = t;
       }
   memcpy(&S[0].v,map,sizeof(map));
}

inline void drop(node *a,int k)
{
   int i,j;
   for(i = j = 0;i < 7;i ++)
       if(a->v[k][i] != 0)
           a->v[k][j ++] = a->v[k][i];
   for(;j < 7;j ++)
       a->v[k][j] = 0;
}

inline int clean(node *a)   //check whether a board is empty
{
   int i;
   for(i = 0;i < W;i ++)
           if(a->v[i][0] != 0)    return 0;
   return 1;
}

int work(node *p)
{
   static int v[W][H],h[W][H],i,j,k;
   int flag = 0;
   memset(v,0,sizeof(v));
   memset(h,0,sizeof(h));
   for(i = 0;i < W;i ++)
       for(j = 0;j < H;j ++)
       {
           if(j > 0 && p->v[i][j] == p->v[i][j - 1])    h[i][j] = h[i][j - 1] + 1;
           else h[i][j] = 1;
           if(i > 0 && p->v[i - 1][j] == p->v[i][j])    v[i][j] = v[i - 1][j] + 1;
           else v[i][j] = 1;
       }

   for(i = 0;i < W;i ++)
       for(j = 0;j < H;j ++)
       {
           if(p->v[i][j] == 0)    continue;
           if(v[i][j] >= 3)
           {
               flag = 1;
               for(k = 0;k < v[i][j];k ++)
                   p->v[i - k][j] = 0;
           }
           if(h[i][j] >= 3)
           {
               flag = 1;
               for(k = 0;k < h[i][j];k ++)
                   p->v[i][j - k] = 0;
           }
       }

   for(i = 0;i < 5;i ++)
       drop(p,i);
   return flag;
}

void output()
{
   int i;
   for(i = 0;i < N;i ++)
       printf("%d %d %d\n",op[i][0],op[i][1],op[i][2]);
   //printf("===================\n");
   /*for(i = 0;i <= N;i ++)
       ptmap(S + i);*/
}

void dfs(int dep)
{
   //fprintf(stderr,"%d:\n",dep);
   //ptmap(S + dep);
   //if(poss(S + dep) == 0)    return;
   if(dep == N)
   {
       if(clean(S + dep))
       {
           output();
           fclose(stdout);
           exit(0);
       }
       return;
   }
   int i,j,tmp;
   node *p1,*p2;
   p1 = S + dep;
   p2 = S + dep + 1;
   for(i = 0;i < 5;i ++)
       for(j = 0;j < 7;j ++)
       {
           if(i < 4 && p1->v[i][j] != 0 && p1->v[i][j] != p1->v[i + 1][j])
           {
               //fprintf(stderr,"%d 1move %d %d\n",dep,i,j);
               memcpy(p2,p1,sizeof(node));
               p2->v[i][j] = p1->v[i + 1][j];
               p2->v[i + 1][j] = p1->v[i][j];
               drop(p2,i);
               drop(p2,i + 1);
               do
               {
                   tmp = work(p2);
               }
               while(tmp);
               op[dep][0] = i;
               op[dep][1] = j;
               op[dep][2] = 1;
               dfs(dep + 1);
           }
           if(i > 0 && p1->v[i][j] != 0 && p1->v[i - 1][j] == 0)
           {
               memcpy(p2,p1,sizeof(node));
               p2->v[i][j] = 0;
               p2->v[i - 1][j] = p1->v[i][j];
               drop(p2,i);
               drop(p2,i - 1);
               do
               {
                   tmp = work(p2);
               }
               while(tmp);
               //printf("2move %d %d\n",i,j);
               op[dep][0] = i;
               op[dep][1] = j;
               op[dep][2] = -1;
               dfs(dep + 1);
           }
       }
}


void debug()
{
   short k[W][H] = {{},{3, 3, 3, 2},{2, 2, 4},{6, 6, 4, 6},{5, 5, 4, 5}};
   node a;
   memcpy(&a.v,k,sizeof(k));
   ptmap(&a);
   int t;
   //drop(&a,2);
   //ptmap(&a);
   do{
       t = work(&a);
   }while(t);
   ptmap(&a);
}


int main()
{
   freopen("mayan.in","r",stdin);
   freopen("mayan.out","w",stdout);
   init();
   dfs(0);
   //debug();
   printf("-1\n");
   fclose(stdout);
   return 0;
}