记录编号	598094	评测结果	AAAAAT
题目名称	原神一统计划	最终得分	83
用户昵称	袁书杰	是否通过	未通过
代码语言	C++	运行时间	3.026 s
提交时间	2025-01-05 11:28:14	内存使用	3.43 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char a[55][55];
bool flag[100005],flag_for_bfs[55][55][55],tot_for_start;
int colour[55][55],the_total_in_the_main,ans=5e18;
struct node {
	int x,y,tot,dis;
};
int dx[]= {0,0,0,1,-1};
int dy[]= {0,1,-1,0,0};
pair<int,int> start[255];
void dfs(int x,int y) {
	colour[x][y]=the_total_in_the_main;
	for(int i=1; i<=4; i++) {
		int nx=dx[i]+x;
		int ny=dy[i]+y;
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]=='X'&&colour[nx][ny]==0) {
			dfs(nx,ny);
		}
	}
}
pair<int,int> path[255];
void dfs1(int x,int y,int dis,int tot) {
	path[dis]=make_pair(x,y);
	if(dis>ans){
		return;
	}
	if(tot==the_total_in_the_main) {
		ans=min(ans,dis);
		return;
	}
	for(int i=1; i<=4; i++) {
		int nx=x+dx[i];
		int ny=y+dy[i];
		node next;
		next.x=nx;
		next.y=ny;
		next.tot=tot;
		next.dis=dis;
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='.'&&flag_for_bfs[nx][ny][tot]==false) {
			flag_for_bfs[nx][ny][tot]=true;
			if(a[nx][ny]=='X') {
				if(flag[colour[nx][ny]]==false) {
					flag[colour[nx][ny]]=true;
					dfs1(next.x,next.y,next.dis,next.tot+1);
					
					flag_for_bfs[nx][ny][tot]=false;
					flag[colour[nx][ny]]=false;
				}
				else{
					dfs1(next.x,next.y,next.dis,next.tot);
					flag_for_bfs[nx][ny][tot]=false;
				}
			} else {
				dfs1(next.x,next.y,next.dis+1,next.tot);
				flag_for_bfs[nx][ny][tot]=false;
			}
		}
	}
}
signed main() {
	freopen("nl.in","r",stdin);
	freopen("nl.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>a[i][j];
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(colour[i][j]==0&&a[i][j]=='X') {
				start[++tot_for_start]=make_pair(i,j);
				the_total_in_the_main++;
				dfs(i,j);
			}
		}
	}
	for(int i=1; i<=tot_for_start; i++) {
		flag[colour[start[i].first][start[i].second]]=true;
		dfs1(start[i].first,start[i].second,0,1);
		flag[colour[start[i].first][start[i].second]]=false;
	}
	cout<<ans;
	return 0;
}
/*
4 4
X.SX
SSS.
.SSS
XS.X
*/