C++14(g++5.4) 解法, 执行用时: 571ms, 内存消耗: 608K, 提交时间: 2020-03-24 20:31:04

#include<bits/stdc++.h>
using namespace std;
char s[10][10],p[10][10];int ans;
int nt[][2]={{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
int same()
{
	int cnt=0;
	for(int i=1;i<=5;i++)
		for(int j=1;j<=5;j++)
			if(s[i][j]!=p[i][j])	cnt++;
	return cnt;
}
void dfs(int x,int y,int px,int py,int sum)
{
	int c=same();
	if(c==0){
		ans=min(ans,sum);return;
	}
	else if(sum+c/2>ans)	return;
	if(sum>=ans-1)	return;
	for(int i=0;i<8;i++){
		int tx=x+nt[i][0],ty=y+nt[i][1];
		if(tx<=0||ty<=0||tx>5||ty>5||(tx==px&&ty==py))	continue;
		swap(s[tx][ty],s[x][y]);
		dfs(tx,ty,x,y,sum+1);
		swap(s[tx][ty],s[x][y]);
	}
}
int main()
{
	int t;scanf("%d",&t);
	for(int i=1;i<=5;i++){
		for(int j=1;j<i;j++)
			p[i][j]='0';
		for(int j=i;j<=5;j++)
			p[i][j]='1';
	}
	p[3][3]='*';p[5][5]='0';p[4][4]='0';
//	for(int i=1;i<=5;i++)
//		for(int j=1;j<=5;j++)
//			printf("%c%c",p[i][j],j==5?'\n':'\0');
	while(t--){
		int sx,sy;
		for(int i=1;i<=5;i++){
			scanf("%s",s[i]+1);
			for(int j=1;j<=5;j++)
				if(s[i][j]=='*')	sx=i,sy=j;
		}
		ans=16;
		dfs(sx,sy,0,0,0);
		if(ans==16)	printf("-1\n");
		else		printf("%d\n",ans);
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 174ms, 内存消耗: 488K, 提交时间: 2022-10-14 13:26:56

#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
char la[5][6]={"11111","01111","00*11","00001","00000"},st[5][6];
int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1},bj,t,x,y,dxx;
int sb()
{
	int sum=0;
	for(int i=0;i<5;i++)for(int j=0;j<5;j++)sum+=(st[i][j]!=la[i][j]);
	return sum-1;
}
void daxingxing(int step,int xx,int yy)
{
	int sum=sb();
	if(sum==-1)
	{
		bj=1;
		return;
	}
	if(sum+step>dxx)return;
	for(int i=0;i<8;i++)
	{
		int tx=xx+dx[i],ty=yy+dy[i];
		if(tx<0||ty<0||tx>4||ty>4)continue;
		swap(st[xx][yy],st[tx][ty]);
		daxingxing(step+1,tx,ty);
		swap(st[xx][yy],st[tx][ty]);
		if(bj)return;
	}
}
int main()
{
// 	ios::sync_with_stdio(false);
 	cin>>t;
 	while(t--)
 	{
 		bj=0;
 		for(int i=0;i<5;i++)
 		{
 			scanf("%s",st[i]);
			for(int j=0;j<5;j++)if(st[i][j]=='*')x=i,y=j;	
		}
		for(dxx=0;dxx<=15;++dxx)
		{
			daxingxing(0,x,y);
			if(bj)break;
		}
		if(dxx==16)cout<<-1<<endl;
		else cout<<dxx<<endl;
	}
    return 0;
}

C++ 解法, 执行用时: 47ms, 内存消耗: 452K, 提交时间: 2021-12-15 16:53:30

#include <bits/stdc++.h>
using namespace std;
char g[6][6];
int u[12]={1,1,1,1,1,2,2,2,2,3,3,4},v[12]={1,2,3,4,5,2,3,4,5,4,5,5},s[8]={1,1,-1,-1,2,2,-2,-2},t[8]={2,-2,2,-2,1,-1,1,-1},T,ans;
int cc(){
    int b=0,w=0;
    for(int i=0;i<12;++i){
        if(g[u[i]][v[i]]=='1')b++;
        else if(g[u[i]][v[i]]=='0')w++;
    }
    if(g[3][3]=='0')w++;
    return 12-b+w;
}
void dfs(int c,int x,int y) {
    int fe=cc();
    if(c+fe>=ans)return;
    if(!fe){ans=min(ans,c);return;}
    for(int i=0;i<8;i++){
        int xx=x+s[i],yy=y+t[i];
        if(xx>0&&xx<=5&&yy>0&&yy<=5)swap(g[xx][yy],g[x][y]),dfs(c+1,xx,yy),swap(g[xx][yy],g[x][y]);
    }
}
int main(){
	cin>>T;
    while(T--){
        int sx,sy;ans=16;
        for(int i=1;i<=5;i++)for(int j=1;j<=5;j++){cin>>g[i][j];if(g[i][j]=='*')sx=i,sy=j;}
        dfs(0,sx,sy);
        if(ans>15)cout<<-1<<"\n";
        else cout<<ans<<"\n";
    }
    return 0;
}