状压dp,
大概是这题 + 这题
\(~bfs~\)求出联通块(岛屿)，每个联通块就是一个独立的节点，
所以两点的距离也可以用\(~bfs~\)求？
这样其实是错的，\(~bfs~\)出来的不是最短距离，还要用上\(~Floyd~\)。
最后套\(~Hamiton~\)板子即可。

\(Code\):

#include<bits/stdc++.h>
using namespace std;
const int N=51;
const int M=5000;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m,cnt,fr[N][N],d[N][N],ans=INT_MAX,f[1<<17][17];
char mp[N][N];
bool vis[N][N];
void Floyd(){
	for(int k=1;k<=cnt;k++)
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=cnt;j++)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
void bfs(int x,int y){
	queue<int>q1,q2;
	q1.push(x);q2.push(y);
	vis[x][y]=true;
	fr[x][y]=cnt;
	while(!q1.empty()){
		int nx=q1.front();q1.pop();
		int ny=q2.front();q2.pop();
		for(int i=0;i<4;i++){
			int fx=nx+dx[i];
			int fy=ny+dy[i];
			if(fx<1||fy<1||fx>n||fy>m||vis[fx][fy]||mp[fx][fy]!='X')
				continue;
			fr[fx][fy]=cnt;vis[fx][fy]=true;
			q1.push(fx);q2.push(fy);
		}
	}	
}
void BFS(int x,int y){
	queue<int>q1,q2,q3;
	q1.push(x);
	q2.push(y);
	q3.push(0);
	vis[x][y]=true;
	while(!q1.empty()){
		int nx=q1.front();q1.pop();
		int ny=q2.front();q2.pop();
		int len=q3.front();q3.pop();
		for(int i=0;i<4;i++){
			int fx=nx+dx[i];
			int fy=ny+dy[i];
			if(fx<1||fy<1||fx>n||fy>m||vis[fx][fy]||mp[fx][fy]=='.')
				continue;
			d[fr[x][y]][fr[fx][fy]]=min(d[fr[x][y]][fr[fx][fy]],len);
//			cout<<fr[x][y]<<' '<<fr[fx][fy]<<' '<<len+1<<endl;
			vis[fx][fy]=true;
			q1.push(fx);q2.push(fy);q3.push(len+1);
		}
	}	
}
void DP(){
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=cnt;i++)
		f[1<<(i-1)][i]=0;
	for(int i=1;i<(1<<cnt);i++)
		for(int j=1;j<=cnt;j++)if(i>>(j-1)&1)
			for(int k=1;k<=cnt;k++)if((i^(1<<(j-1)))>>(k-1)&1)
				f[i][j]=min(f[i][j],f[i^(1<<(j-1))][k]+d[k][j]);
	for(int i=1;i<=cnt;i++)
		ans=min(ans,f[(1<<cnt)-1][i]);	
	printf("%d",ans);
}
int main(){
	memset(d,0x3f,sizeof(d));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>mp[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(vis[i][j]||mp[i][j]!='X')continue;
			cnt++;bfs(i,j);
        }
    memset(vis,0,sizeof(vis));
//    for(int i=1;i<=n;i++){
//    	for(int j=1;j<=m;j++)
//    		if(mp[i][j]!='X')cout<<mp[i][j]<<' ';
//    		else cout<<fr[i][j]<<' ';
//    	cout<<endl;
//	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(mp[i][j]!='X')continue;
			memset(vis,0,sizeof(vis));
			d[i][i]=0;BFS(i,j);
		}
//	for(int i=1;i<=cnt;i++){
//		for(int j=1;j<=cnt;j++)
//			printf("%d---->%d: %d\n",i,j,d[i][j]);
//	}
	Floyd();
	DP();
	return 0;
}
/*
4 5
...XX
.XXX.
X...X
.XXXX
*/
/*
2 5
. . . 1 1
. 2 2 X .
*/