题解 P1312 【Mayan游戏】

QWsin · 2015-12-07 13:18:05 · 题解

纯暴搜题 但是代码好长QAQ 耗时三个半小时（一场noip）

主要是一个很实用的剪枝 ： 左边不为空就不往左边移 因为这样等价于把左边的右移 后者更优 就加了这个剪枝就能过了 自己认为我的常数还是比较大的= =

别的没什么 调试的时候一定要耐心啊= = 对着样例调都找了一个小时

是这样的 一开始 回溯后用来将局面还原的数组开成了全局变量= = 就只能存一个了

然后 下降函数出问题了= = 无法处理一块掉下多个空格的情况

中途顺便发现了 应该先处理右移再处理左移

然后 清除函数又写错了QAQ 什么都错真是醉了 清除用的dfs找连通块个数是否大于三

结果看题发现必须要横竖有三个才行 这样的话= =横着一次暴搜竖着一次暴搜加一个bool数组解决

细节比较多 容易出错 而且还不好改= = 但是暴搜题就是这样坑爹

特别想%一下当场A掉的神犇

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=8;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
struct Point{
    int x,y;
    Point(int x,int y):x(x),y(y){}
    Point(){}
};

int map[maxn][maxn],cnt[20],x[maxn],y[maxn],ins[maxn];
int n;

void init_data()
{
    cin>>n;
    for(int i=1;i<=5;i++)
      for(int j=1;;j++)
      {
          scanf("%d",&map[i][j]);
          if(map[i][j]==0) break;
          cnt[map[i][j]]++;
      }
}

void change(int &a,int &b){int tmp=a;a=b;b=tmp;}

void down()
{
    int tmp[10];
    for(int i=1;i<=5;i++)
    {
        int cnt=1;
         for(int j=1;j<=7;j++)
         {
             if(map[i][j])
               tmp[cnt++]=map[i][j];
             map[i][j]=0;
        }  
         for(int j=1;j<=cnt-1;j++)
          map[i][j]=tmp[j];
    }

}

int vis[maxn][maxn];
bool dfs(int x,int y,int &cnt,int st)
{
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(map[nx][ny]&&map[nx][ny]==st&&!vis[nx][ny])
        {
            int tmp=map[nx][ny];
            map[nx][ny]=0;
            vis[nx][ny]=1;
            dfs(nx,ny,++cnt,st);
            vis[nx][ny]=0;
            if(cnt<3) 
            {
                map[nx][ny]=tmp;
            }
        }
    }
    vis[x][y]=0;
    if(cnt<3)return false;
    return true;
}

int can[maxn][maxn];
bool clean()
{
    memset(can,0,sizeof(can));
    int p=0;
    for(int i=1;i<=5;i++)
      for(int j=1;j<=7-2;j++)
        if(map[i][j]&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j+2])
        {
            p=1;
            int tmp=j+3;
            can[i][j]=can[i][j+1]=can[i][j+2]=1;
              while(tmp<=7&&map[i][tmp]==map[i][j]) 
            {
                can[i][tmp]=1;tmp++;
            }
        }
    for(int j=1;j<=7;j++)
      for(int i=1;i<=5-2;i++)  
        if(map[i][j]&&map[i][j]==map[i+1][j]&&map[i+2][j]==map[i][j])
        {
            p=1;
            int tmp=i+3;
            can[i][j]=can[i+1][j]=can[i+2][j]=1;
              while(tmp<=5&&map[tmp][j]==map[i][j]) 
            {
                can[tmp][j]=1;tmp++;
            }
        }
    if(!p) return false;
    for(int i=1;i<=5;i++)
      for(int j=1;j<=7;j++)
        if(can[i][j])
          map[i][j]=0;
    return true;
}

void move_block(int ii,int jj,int wh)
{
    change(map[ii+wh][jj],map[ii][jj]);
    for(;;){
        down();
        if(!clean()) break;
    }
}

int check()
{
    int ok=1;
    for(int i=1;i<=5;i++)
      for(int j=1;j<=7;j++)
        if(map[i][j]) ok=0;
    return ok;
}

bool solve(int d)
{
    int mm[maxn][maxn];
    if(d>n) 
    {
        do{
            down();
        }while(clean());
        if(check()) return true;
        return false;
    }
    int p=1;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
          if(map[i][j]!=0)
          {
              p=0; 
            if(i<5)
            {    
                memcpy(mm,map,sizeof(map));
                x[d]=i;y[d]=j;
                ins[d]=1;
                move_block(i,j,1);
                if(!solve(d+1)) 
                {
                    memcpy(map,mm,sizeof(mm));
                      x[d]=y[d]=ins[d]=0;
                }
                else
                {
                    return true;
                }
            }
            if(i>1&&map[i-1][j]==0) 
            {
                memcpy(mm,map,sizeof(map));
                x[d]=i;y[d]=j;
                ins[d]=-1;
                  move_block(i,j,-1);
                  if(solve(d+1)) return true;
                  else
                  {
                      memcpy(map,mm,sizeof(mm));
                      x[d]=y[d]=ins[d]=0;
                }
            }
          }
    }
    if(p) return true;
    return false;
}

void print_ans()
{
    for(int i=1;i<=n;i++)
      printf("%d %d %d\n",x[i]-1,y[i]-1,ins[i]);
}

int main()
{
    init_data();
     if(solve(1)) print_ans();
    else printf("-1");
    return 0;
}