题目链接

题目来自洛谷

话说这个题真的恶心到我了,耗时一天半拿到90,最后一个点吸氧过的。

主要用到的就是搜索回溯,重点倒不是在于那几个优化,而是怎么划分层次,怎么把代码写清晰,因为这道题实在太麻烦了,这里极建议把能摘出去做函数的部分全摘出去,开始写的时候最好先写大框架,类似于(这里是这道题dfs的框架):

	if(chack()==1){
		for(int i=1;i<=n;i++){
		}
		exit(0);
	}
	if(nx==n+1)	return;
	copy(nx);
	for(int i=1;i<=5;i++){
		for(int j=1;j<=7;j++){
			if(i!=1&&a[i-1][j]==0){
				move(i-1,i,j);
				dfs(nx+1);
				copy_return(nx);
			}
			if(i!=5&&a[i][j]!=a[i+1][j]){
				move(i+1,i,j);
				dfs(nx+1);
				copy_return(nx);
			}
		}
	}

然后把你想加进去的move函数等等写在上面。

我的思路:找到一个点,交换,到步数后检查行不行。

几个子函数意思:

chack:检查方格内是否全是0

copy:走到nx步时的方格的样子

find0:将这里横向或竖向可以消除的格子做上标记,因为类似十字形的消除一行后本该消去的另一行就无法消去了,所以要先全部标记。因为标记+消除后形成的新局势可能还有可以消的,所以用到了while,jihao为0时跳出。

luoxia:消除,向上找到一个不该消且不为0的数交换,找不到就直接置为0,模仿合法格子下降。

copy_return:回溯时恢复原状用

move:交换两个格子的值,此时需要先luoxia();再while(find0())  luoxia();因为交换后格局又变了,可能存在有数的格子与0交换的情况,需要先把此悬空格子放下再下一步。(血的教训

xx[],yy[].vv[]存位置,最后-1,因为原文是从(0,0)开始的。

说说我踩的坑吧:

1.find0函数中,计数numm置为0的位置写在第二层循环中了,把numm在a[i][j]!=a[i][j-1]时的置为一写在numm>=3中了,横向搜索时,因为最后一行不可能出现有值与它不一样了,0 0 4 4 4时4 4 4就不会被消去,此时把5->6就可以了,因为第6列是0.

2.&&和||打反的问题

3.break的应用:在luoxia函数中,本来找到一个可替代的数交换后就该停止进行下一个,我没写,,就惨了。

一些优化:

1.chack函数中只要搜最后一行有没有数就行了

2.dfs时,只与左边交换,右边为0时才交换,因为这个格子与它右边格子交换=右边格子与它交换,而且1和-1,与右交换字典序更小。(注意边界问题

3.dfs遇见某数==0时直接break,此时再往下该列dfs也都是0了。

代码(这绝对是我写过的最有层次感的代码

//这道题我做了一天了还是没做出来我现在很烦 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int cop[6][6][9],a[6][9],xx[8],yy[8],vv[8],fl[7][8];
int jihao,n;
int chack(){
    for(int i=1;i<=5;i++){
        if(a[i][1]!=0)    return 0;
    }
    return 1;
}
void copy(int nx){
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            cop[nx][i][j]=a[i][j];
        }
    }
}

int find0(){
    memset(fl,0,sizeof(fl));
    jihao=0;
    for(int i=1;i<=5;i++){
        int numm=0;
        for(int j=1;j<=7;j++){
            if(a[i][j]==a[i][j-1])    numm++;
            else {
                if(numm>=3){
                    jihao=1;
                    int now=j-1;
                    while(numm){
                        fl[i][now]=1;
                        now--;
                        numm--;
                    }

                }
                numm=1;
            }
        }
    }
    for(int i=1;i<=7;i++){
        int numm=0;
        for(int j=1;j<=6;j++){
            if(a[j][i]==a[j-1][i]) numm++;
            else {
                if(numm>2&&a[j-1][i]!=0){
                    jihao=1;
                    int now=j-1;
                    while(numm){
                        fl[now][i]=1;
                        now--;
                        numm--;
                    }
                }
                numm=1;
            }
            if(a[j][i]==0)    numm=1;
            if(numm>2)    jihao=1;
        }
    }
    if(jihao==1)    return 1;
    return 0;
}
void luoxia(){
    jihao=0;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            jihao=0;
            if(fl[i][j]==1||a[i][j]==0){
                for(int k=j+1;k<=7;k++){
                    if(a[i][k]!=0&&fl[i][k]!=1){
                        jihao=1;
                        int tmp=a[i][k];
                        a[i][k]=0;
                        a[i][j]=tmp;
                        break;
                    }
                }
                if(jihao==0)    a[i][j]=0,fl[i][j]=0;
            }
        }
    }
}
void copy_return(int nx){
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            a[i][j]=cop[nx][i][j];
        }
    }
}
void move(int x1,int x2,int y){
    int tmp=a[x1][y];
    a[x1][y]=a[x2][y];
    a[x2][y]=tmp;
    luoxia();
    while(find0())
        luoxia();
}
void dfs(int nx){
    while(find0())
        luoxia();
    if(chack()==1){
        for(int i=1;i<=n;i++){
            printf("%d %d %d",xx[i],yy[i],vv[i]);
            printf("\n");
        }
        exit(0);
    }
    if(nx==n+1)    return;
    copy(nx);
    for(int i=1;i<=5;i++){
        for(int j=1;j<=7;j++){
            if(a[i][j]==0)    break;
            if(i!=1&&a[i-1][j]==0){
                move(i-1,i,j);
                xx[nx]=i-1;
                yy[nx]=j-1;
                vv[nx]=-1;
                dfs(nx+1);
                copy_return(nx);
                xx[nx]=0;
                yy[nx]=0;
                vv[nx]=0;
            }
            if(i!=5&&a[i][j]!=a[i+1][j]){
                move(i+1,i,j);
                xx[nx]=i-1;
                yy[nx]=j-1;
                vv[nx]=1;
                dfs(nx+1);
                copy_return(nx);
                xx[nx]=0;
                yy[nx]=0;
                vv[nx]=0;
            }
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=5;i++){
        int cnt=0;
        while(1){
            int opt;
            scanf("%d",&opt);
            if(opt==0)    break;
            cnt++;
            a[i][cnt]=opt;//cnm
        }
    }
    dfs(1);
    printf("-1");
    return 0;
}
View Code
01-21 03:18