自动搬运

查看原文

来自洛谷，原作者为

	Xiao_Mi .

搬运于2025-08-24 21:36:38，当前版本为作者最后更新于2018-07-28 12:35:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题可以用迭代加深搜索来做

用ans枚举多少步可以达到棋局，然后再dfs，若超过ans就返回，一直到可移动到目标棋局为止。

这样就不会超时了。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[11][11],ans;
int fkx[5]={0,-1,1,0,0},
	fky[5]={0,0,0,-1,1};
int check(){//查看是否到目标棋局
	for(int i=1;i<=4;i++){
        if(a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][3]==a[i][4]) return 1;
        if(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[3][i]==a[4][i]) return 1;
    }
    if(a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4]) return 1;
    if(a[1][4]==a[2][3]&&a[2][3]==a[3][2]&&a[3][2]==a[4][1]) return 1;
    return 0;
}
int dfs(int x,int y,int xx,int yy,int color,int teg){//color：上一组的颜色，teg：第几层
	if(ans==teg){
		if(check()) return 1;
		else return 0;
	}
	for(int i=1;i<=4;i++){
		int dx=fkx[i]+x;
		int dy=fky[i]+y;
		int ddx=fkx[i]+xx;
		int ddy=fky[i]+yy;
		if(dx>0&&dx<=4&&dy>0&&dy<=4&&a[dx][dy]!=color){
			swap(a[x][y],a[dx][dy]);
			if(dfs(dx,dy,xx,yy,(color==1?2:1),teg+1)) return 1;;
			swap(a[dx][dy],a[x][y]);
		}
		if(ddx>0&&ddx<=4&&ddy>0&&ddy<=4&&a[ddx][ddy]!=color){
			swap(a[xx][yy],a[ddx][ddy]);
			if(dfs(x,y,ddx,ddy,(color==1?2:1),teg+1)) return 1;
			swap(a[ddx][ddy],a[xx][yy]);
		}
	}
	return 0; 
}
int main(){
	int i,j,fx1=0,fy1=0,fx2=0,fy2=0;
	char c;
	for(i=1;i<=4;i++){
		for(j=1;j<=4;j++){
			cin>>c;
			if(c=='B') a[i][j]=1;
			if(c=='W') a[i][j]=2;
			if(c=='O') a[i][j]=0;
			if(a[i][j]==0&&!fx1) fx1=i,fy1=j;
            else if(a[i][j]==0) fx2=i,fy2=j;
		}
	}
    //枚举多少步可到达棋局
	for(ans=1;ans<=0x3f3f3f;ans++){
   	 //先黑再白，注意顺序
		if(dfs(fx1,fy1,fx2,fy2,1,0)) break;
		if(dfs(fx1,fy1,fx2,fy2,2,0)) break;
	}
	cout<<ans;
	return 0; 
}