66分求调QAQ
查看原帖
66分求调QAQ
602932
NumberTrart楼主2024/3/2 22:53
#include<iostream>
#include<cmath>
using namespace std;
char a[7][7],b[7][7];
int cnt1,cnt0,minn=2e9;
struct xy
{
	int x,y;
} one[25],zero[25];
bool vis[25];
string anstring="404 not found";
int dist(xy a,xy b)
{
	return abs(a.x-b.x)+abs(a.y-b.y);
}
string distring(xy a,xy b)
{
	string ret="";
	while(a.x<b.x)
	{
		ret+=char('0'+a.x);
		ret+=char('0'+a.y);
		a.x++;
		ret+=char('0'+a.x);
		ret+=char('0'+a.y);
		ret+='\n';
	}
	while(a.x>b.x)
	{
		ret+=char('0'+a.x);
		ret+=char('0'+a.y);
		a.x--;
		ret+=char('0'+a.x);
		ret+=char('0'+a.y);
		ret+='\n';
	}
	while(a.y<b.y)
	{
		ret+=char('0'+a.x);
		ret+=char('0'+a.y);
		a.y++;
		ret+=char('0'+a.x);
		ret+=char('0'+a.y);
		ret+='\n';
	}
	while(a.y>b.y)
	{
		ret+=char('0'+a.x);
		ret+=char('0'+a.y);
		a.y--;
		ret+=char('0'+a.x);
		ret+=char('0'+a.y);
		ret+='\n';
	}
	return ret;
}
void dfs(int n,int len,string ans)
{
	if(len>=minn) return;
	if(n==cnt1+1)
	{
		minn=len;
		anstring=ans;
		return;
	}
	for(int i=1;i<=cnt1;i++)
		if(!vis[i])
		{
			vis[i]=true;
			dfs(n+1,len+dist(zero[n],one[i]),ans+distring(zero[n],one[i]));
			vis[i]=false;
		}
}
int main()
{
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			cin>>a[i][j];
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			cin>>b[i][j];
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			if(a[i][j]=='1'&&b[i][j]=='0')
				one[++cnt1]=xy{i,j};
			else if(a[i][j]=='0'&&b[i][j]=='1')
				zero[++cnt0]=xy{i,j};
	if(cnt1!=cnt0)
		return 1;
	if(cnt1==0)
	{
		cout<<'0';
		return 0;
	}
	dfs(1,0,"");
	cout<<minn<<'\n'<<anstring;
	if(anstring=="404 not found") return 2;
	return 0;
}

我心想有没有可能是zero和one的问题,于是我交换了一下它俩,44分

2024/3/2 22:53
加载中...