求助(能A但其他OJ挂了)
查看原帖
求助(能A但其他OJ挂了)
1129446
nksunhaolan楼主2024/11/23 22:04
#include <bits/stdc++.h>
using namespace std;

const int N=900;

int n,m,kx,ky;
int dis[50][50][2];
bool vis[50][50];
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
int kinx[9]={-1,-1,-1,0,0,0,1,1,1};
int kiny[9]={-1,0,1,-1,0,1,-1,0,1};
int get(const int& sx,const int& sy,const int& ex,const int& ey){
	return max(abs(sx-ex),abs(sy-ey));
}
struct nnd {
	int x,y;
}A[N];
int cnt;
struct node {
	int x,y,w;
	bool operator > (const node& a) const {
		return w > a.w ;
	}
};
priority_queue<node,vector<node>,greater<node> >q;

void djs(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1][1][0]=0;
	q.push({1,1,0});
	int k=0;
	while(!q.empty()){
		int x=q.top().x,y=q.top().y;
		q.pop();
		if(vis[x][y])continue;
		else vis[x][y]=1;
		for(int i=0;i<8;i++){
			int tx=dx[i]+x,ty=dy[i]+y;
			if(tx<1 || tx>n || ty<1 || ty>m){
				continue;
			}
			if(dis[tx][ty][k]>dis[x][y][k]+1){
				dis[tx][ty][k]=dis[x][y][k]+1;
				q.push({tx,ty,dis[tx][ty][k]});
			}
		}
	}
	memset(vis,0,sizeof(vis));
	dis[2][2][1]=0;
	q.push({2,2,0});
	k=1;
	while(!q.empty()){
		int x=q.top().x,y=q.top().y;
		q.pop();
		if(vis[x][y])continue;
		else vis[x][y]=1;
		for(int i=0;i<8;i++){
			int tx=dx[i]+x,ty=dy[i]+y;
			if(tx<1 || tx>n || ty<1 || ty>m){
				continue;
			}
			if(dis[tx][ty][k]>dis[x][y][k]+1){
				dis[tx][ty][k]=dis[x][y][k]+1;
				q.push({tx,ty,dis[tx][ty][k]});
			}
		}
	}
}
int get_dis(int sx,int sy,int ex,int ey){
	if(ex<sx){
		swap(sx,ex);
		swap(sy,ey);
	}
	if(sy>ey){
		sy=m-sy+1;
		ey=m-ey+1;
	}
	if(sx==1 && sy==1){
		return dis[ex][ey][0];
	} else {
		return dis[ex-sx+2][ey-sy+2][1];
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	char s;
	cin>>m>>n;
	
	cin>>s>>ky;
	kx=s-'A'+1;
	while(cin>>s>>A[++cnt].y){
		A[cnt].x=s-'A'+1;
	}
	if(cnt==1){
		cout<<"0";
		return 0;
	}
	djs();
	long long ans=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			long long sum=get(kx,ky,i,j);
			for(int k=1;k<cnt;k++){
				int x=A[k].x,y=A[k].y;
				sum+=get_dis(x,y,i,j);
			}
			for(int k=1;k<cnt;k++){
				int x=A[k].x,y=A[k].y;
				for(int t=0;t<9;t++){
					int tx=kx+kinx[t],ty=ky+kiny[t];
					if(tx<1 || tx>n || ty<1 || ty>m){
						continue;	
					}
					ans=min(ans,sum-get_dis(x,y,i,j)-get(kx,ky,i,j)+get_dis(tx,ty,x,y)+get_dis(tx,ty,i,j)+(tx!=kx||ty!=ky));
				}
			}
		}
	}
	cout<<ans;
	
	return 0;
}
2024/11/23 22:04
加载中...