听取WA声一片
查看原帖
听取WA声一片
1020566
prg_equal_depressed楼主2024/7/3 13:29
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
int n,m,cnt[55][55],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},spt,s1,s2=3000,dis[4];
string map[55];
void dfs(int x,int y,int spt){
	cnt[x][y]=spt;
	for (int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if (!cnt[nx][ny]&&map[nx][ny]=='X'){
			dfs(nx,ny,spt);
		}
	}
	return;
}
int dist(int x,int y){
	int minn=3000;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			for (int k=1;k<=n;k++){
				for (int l=1;l<=m;l++){
					if ((cnt[i][j]==x&&cnt[k][l]==y)||(cnt[i][j]==y&&cnt[k][l]==x)){
						minn=min(minn,abs(i-k)+abs(j-l)-1);
					}
				}
			}
		}
	}
	return minn;
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		cin>>map[i];
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (!cnt[i][j]&&map[i][j]=='X'){
				dfs(i,j,++spt);
			}
		}
	}
	s1=min(dist(1,2)+dist(2,3),min(dist(2,3),dist(1,2)+dist(1,3)));
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (!cnt[i][j]){
				memset(dis,3000,sizeof(dis));
				for (int k=1;k<=n;k++){
					for (int l=1;l<=m;l++){
						if (cnt[k][l]){
							dis[cnt[k][l]]=min(dis[cnt[k][l]],abs(i-k)+abs(j-l)-1);
						}
					}
				}
				s2=min(s2,dis[1]+dis[2]+dis[3]+1);
			}
		}
	}
	cout<<min(s1,s2);
	return 0;
}

33分玄关,蒟蒻在线等,急

2024/7/3 13:29
加载中...