NOIP 2011 Mayan game search

Topic link: https://www.luogu.org/problemnew/show/P1312

My first question solution!!

Of course, thanks. ZAGER , his link https://www.cnblogs.com/ZAGER/p/9535526.html

 

This question is a big search, which really tests my code ability

It's a good habit to write functions with clear ideas.

Step by step

Define map[i][j] to represent the current map, last[x][i][j] to represent the original map in step x, and ans[x][i] to record the operation in step X

 

check() to check whether it has been eliminated. Of course, according to the rule, you only need to check whether the bottom line has been eliminated;

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

During the drop process of update(), we search from the bottom to the top to record several empty lines below the current map when it has values

void update()//Drop process 
{
    for(int i=1;i<=5;i++)
    {
        int down=0;
        for(int j=1;j<=7;j++)
        {
            if(!map[i][j]) down++;
            else
            {
                if(!down) continue;
                map[i][j-down]=map[i][j];
                map[i][j]=0;
            }
        }
    }
}

The point is here (for me)

 

The operation of changing movement did not take a good look at the problem. When moving, you can not only exchange with other squares, but also drag them to the air and then drop them. Therefore, you should check the drop after exchanging

void move(int x,int y,int z)//Transformation Mobile 
{
    int mem=map[x][y];
    map[x][y]=map[x+z][y];
    map[x+z][y]=mem;
    update();
    while(remove()) update();//Drop after elimination 
}

remove() is used for the elimination process. In order to meet the condition in Figure 5, we first record the elimination.

int remove()//Elimination process 
{
    bool flag=0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(i>=2&&i<=4&&map[i][j]&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j])
            {
                xx[i-1][j]=1;xx[i][j]=1;xx[i+1][j]=1;flag=1;
            }
            if(j>=2&&j<=6&&map[i][j]&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1])
            {
                xx[i][j]=1;xx[i][j-1]=1;xx[i][j+1]=1;flag=1;
            }
        }
    }//Record first and then eliminate to meet the situation in Figure 5 
    if(!flag) return 0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(xx[i][j])
            {
                map[i][j]=0;
                xx[i][j]=0;
            }
        }
    }
    return 1;
}

 

There are also a few trivial (and important) small functions with comments in the code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n;
int map[10][10],last[10][10][10],ans[10][5];//map Current map,; last The next step is to move the map; ans Yes, the first step and the second answer 
int xx[10][10];
bool check()
{
    for(int i=1;i<=5;i++)
    {
        if(map[i][1]) return 0;
    }
    return 1;
}

void  memory(int x)
{
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            last[x][i][j]=map[i][j];//Record No. x The original appearance of step time map 
        }
    }
}

void update()//Drop process 
{
    for(int i=1;i<=5;i++)
    {
        int down=0;
        for(int j=1;j<=7;j++)
        {
            if(!map[i][j]) down++;
            else
            {
                if(!down) continue;
                map[i][j-down]=map[i][j];
                map[i][j]=0;
            }
        }
    }
}

int remove()//Elimination process 
{
    bool flag=0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(i>=2&&i<=4&&map[i][j]&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j])
            {
                xx[i-1][j]=1;xx[i][j]=1;xx[i+1][j]=1;flag=1;
            }
            if(j>=2&&j<=6&&map[i][j]&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1])
            {
                xx[i][j]=1;xx[i][j-1]=1;xx[i][j+1]=1;flag=1;
            }
        }
    }//Record first and then eliminate to meet the situation in Figure 5 
    if(!flag) return 0;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(xx[i][j])
            {
                map[i][j]=0;
                xx[i][j]=0;
            }
        }
    }
    return 1;
}
void move(int x,int y,int z)//Transformation Mobile 
{
    int mem=map[x][y];
    map[x][y]=map[x+z][y];
    map[x+z][y]=mem;
    update();
    while(remove()) update();//Drop after elimination 
}

void recover(int x)
{
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            map[i][j]=last[x][i][j];
        }
    }
    ans[x][1]=0;ans[x][2]=0;ans[x][3]=0;
}
void dfs(int x)
{
    if(check())
    {
        for(int i=1;i<=n;i++)
        {
            if(i!=1) printf("\n");
            for(int j=1;j<=3;j++)
            {
                printf("%d ",ans[i][j]);
            }
        }
        exit(0);
    }
    if(x==n+1) return ;
    memory(x);
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=7;j++)
        {
            if(map[i][j])
            {
                if(i<=6&&map[i][j]!=map[i+1][j])
                {
                    move(i,j,1);
                    ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1;
                    dfs(x+1);
                    recover(x);//Restore original map and ans 
                }
            }
            if(i>=2&&(!map[i-1][j]))
            {
                move(i,j,-1);
                ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1;
                dfs(x+1);
                recover(x);
            }
        }
    }

    
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=8;j++)
        {
            int x;
            scanf("%d",&x);
            if(x==0) break;
            map[i][j]=x;
        }
    }
    dfs(1);
    printf("-1\n");
    return 0;
}

Keywords: C++ Mobile

Added by Amitk on Fri, 15 Nov 2019 22:59:36 +0200