P1312 [NOIP 2011 提高组] Mayan 游戏题解

hexuchen · 2025-02-06 17:33:54 · 题解

题目传送门

更好的阅读体验？

题目大意

一款消消乐游戏，有 7 \times 5 的棋盘。每次可以横向挪动一个方块，相同颜色的 3 个方块可以消除。求消除所有方块的最小次数。

思路分析

一道毒瘤的模拟、深搜题。

此题思路不难。枚举每一个方块所有可能的移动，用 dfs 搜索即可。回溯有些麻烦，要先用一个辅助数组存下原数组，回溯时将原数组的值替换成辅助数组的值。

注意直接搜索会 TLE，所以要加剪枝。在向左移动方块时要判断左边是否为空。如果为空，则没有移动的必要，直接退出。

坑点见此贴

代码分解

这题难难在代码上。为了方便，本题解采用数组的顺序存储棋盘，即左上角的坐标是 (1,1)。

注：只展示重要的函数，零散小函数不展示

down 函数

该函数用于实现将某一个方块落下。

void down(int x,int y){
    if(s[x][y]==0){ //格子为空则没必要下落
        return ;
    }
    for(int i=x;i<7;i++){ //遍历到底部
        if(s[i+1][y]==0){ //下面为空
            swap(s[i+1][y],s[i][y]);
        }
        else{ //落到方块上了
            break;
        }
    }
}

move 函数

该函数用于移动方块。

void move(int x,int y,int r,int c){
    swap(s[x][y],s[r][c]); //交换方块位置
    down(r,c);
    for(int i=x-1;i>=1;i--){ //方块下落
        down(i,y);
    }
}

proccess 函数

该函数用于消除 3 个连着的方块并下落。但是题目有一个坑：

（如图 5）当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除

所以判断不能直接在原数组上判断，要用辅助数组进行判断，原数组进行消除。

void proccess(){
    a_to_b(s,s2); //这是自己定义的一个简单函数，负责将原数组 s 的值复制给辅助数组 s2
    for(int i=1;i<=7;i++){ //横向的三个
        for(int j=1;j<=3;j++){
            if(s2[i][j]==s2[i][j+1] && s2[i][j+1]==s2[i][j+2]){ //有三个连在一起的，注意用辅助数组判断
                s[i][j]=s[i][j+1]=s[i][j+2]=0; //用原数组消除
            }
        }
    }
    for(int i=1;i<=5;i++){ //纵向的三个
        for(int j=1;j<=5;j++){
            if(s2[j+1][i]==s2[j+2][i] && s2[j+2][i]==s2[j+3][i]){
                s[j+1][i]=s[j+2][i]=s[j+3][i]=0;
            }
        }
    }
    for(int i=7;i>=1;i--){ //记得下落
        for(int j=1;j<=5;j++){
            down(i,j);
        }
    }
}

dfs 函数

void dfs(int step){
    if(check()){ //check 负责判断棋盘是否全空
        print(); //print 负责输出
        return ;
    }
    if(step>n){ //步数超了
        return ;
    }
    int s3[8][6]; //辅助数组，负责回溯
    for(int j=1;j<=5;j++){ //先列再行
        for(int i=7;i>=1;i--){ //从大到小（因为代码是倒着存的，这样可以使字典序最小）
            if(s[i][j]==0){
                continue;
            }
            if(j<=4){ //可以右移
                a_to_b(s,s3); //辅助数组更新
                ans1[step]=j-1;
                ans2[step]=7-i;
                ans3[step]=1;
                move(i,j,i,j+1); //移方块
                for(int k=1;k<=(num/3+1);k++){ //注意可能会存在连续消除的情况，num 为方块个数
                    proccess();
                }
                dfs(step+1);
                a_to_b(s3,s); //回溯
            }
            if(j>=2 && s[i][j-1]==0){ //左移，剪枝
                a_to_b(s,s3);
                ans1[step]=j-1;
                ans2[step]=7-i;
                ans3[step]=-1;
                move(i,j,i,j-1);
                for(int k=1;k<=(num/3+1);k++){
                    proccess();
                }
                dfs(step+1);
                a_to_b(s3,s);
            }
        }
    }
}

AC 代码

#include <bits/stdc++.h>
using namespace std;
int n,s[8][6],s2[8][6],ans1[6],ans2[6],ans3[6],num=0;
void a_to_b(int (&a)[8][6],int (&b)[8][6]){
    for(int i=1;i<=7;i++){
        for(int j=1;j<=5;j++){
            b[i][j]=a[i][j];
        }
    }
}
void down(int x,int y){
    if(s[x][y]==0){
        return ;
    }
    for(int i=x;i<7;i++){
        if(s[i+1][y]==0){
            swap(s[i+1][y],s[i][y]);
        }
        else{
            break;
        }
    }
}
void move(int x,int y,int r,int c){
    swap(s[x][y],s[r][c]);
    down(r,c);
    for(int i=x-1;i>=1;i--){
        down(i,y);
    }
}
void proccess(){
    a_to_b(s,s2);
    for(int i=1;i<=7;i++){
        for(int j=1;j<=3;j++){
            if(s2[i][j]==s2[i][j+1] && s2[i][j+1]==s2[i][j+2]){
                s[i][j]=s[i][j+1]=s[i][j+2]=0;
            }
        }
    }
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            if(s2[j+1][i]==s2[j+2][i] && s2[j+2][i]==s2[j+3][i]){
                s[j+1][i]=s[j+2][i]=s[j+3][i]=0;
            }
        }
    }
    for(int i=7;i>=1;i--){
        for(int j=1;j<=5;j++){
            down(i,j);
        }
    }
}
bool check(){
    for(int i=1;i<=7;i++){
        for(int j=1;j<=5;j++){
            if(s[i][j]!=0){
                return false;
            }
        }
    }
    return true;
}
void print(){
    for(int i=1;i<=n;i++){
        cout<<ans1[i]<<' '<<ans2[i]<<' '<<ans3[i]<<'\n';
    }
    exit(0);
}
void dfs(int step){
    if(check()){
        print();
        return ;
    }
    if(step>n){
        return ;
    }
    int s3[8][6];
    for(int j=1;j<=5;j++){
        for(int i=7;i>=1;i--){
            if(s[i][j]==0){
                continue;
            }
            if(j<=4){
                a_to_b(s,s3);
                ans1[step]=j-1;
                ans2[step]=7-i;
                ans3[step]=1;
                move(i,j,i,j+1);
                for(int k=1;k<=(num/3+1);k++){
                    proccess();
                }
                dfs(step+1);
                a_to_b(s3,s);
            }
            if(j>=2 && s[i][j-1]==0){
                a_to_b(s,s3);
                ans1[step]=j-1;
                ans2[step]=7-i;
                ans3[step]=-1;
                move(i,j,i,j-1);
                for(int k=1;k<=(num/3+1);k++){
                    proccess();
                }
                dfs(step+1);
                a_to_b(s3,s);
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=5;i++){
        int a;
        for(int j=7;j>=0;j--){
            cin>>a;
            if(a==0){
                break;
            }
            s[j][i]=a;
            num++;
        }
    }
    dfs(1);
    cout<<-1;
    return 0;
}