题解：P3070 [USACO13JAN] Island Travels G

场切的第四题蓝。
## 预处理岛屿编号
要处理出：
- 设 $id_{x,y}$ 表示 $(i,j)$ 属于哪个岛，为 $0$ 表示不是陆地。
- $tot$：岛的数量。

用 $DFS$ 就可以求出来
## 预处理岛屿两两之间的距离
$Y_{x,y}$：$x$ 和 $y$ 两个岛，至少经过几次浅水。

$BFS$ 即可，但很恶心。
## 算出答案
状压 $dp$。设 $f_{x,y}$ 为走过的岛为 $x$，最后一次走到是 $y$ 的最小花费。

初始化 $f_{0,x}$ 为 $0$，其他都为无穷大。$dp$ 时可以使用刷表法，也可以使用填表法。我用的是填表法。

最后答案即为 $\min_{i=1}^n\{f_{2^n-1,i}\}$。
## 时间复杂度
- 状压 $dp$：题目保证岛屿数量 $\le15$（表示为 $k$），时间复杂度为 $O(2^k\times k^2)$。
- 预处理岛屿编号：$O(n^2)$。
- 预处理岛屿两两之间的距离：$O(k^2\times n^2\times\log n)$。
## code
```cpp
//Do not hack it
// @author       fkxr(luogu uid=995934)
#include <bits/stdc++.h>
#define endl cerr<<"------------------I Love Sqrt Decomposition------------------\n";
#define int long long
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#define ds(x) (x=='\r'||x=='\n'||x==' ')
#define MAX 20
namespace fastIO {
	template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; }
	template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[MAX]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); }
	struct Srr {
		inline Srr operator>>(int& a) { r(a); return{}; }
		inline Srr operator>>(char& ch) { ch = gc(); for (; ds(ch);)ch = gc(); return{}; }
		inline Srr operator>>(string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; !(ds(ch) || ch == EOF);) { s.push_back(ch); ch = gc(); }return{}; }
		template<typename T>inline Srr operator<<(T& a) { r(a); return{}; }
		inline void is(int n, string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; n--;) { s.push_back(ch); ch = gc(); } }
	}in;
	struct Sww {
		inline Sww operator<<(const int a) { w(a); return{}; }
		inline Sww operator<<(const char ch) { pc(ch); return{}; }
		inline Sww operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; }
		template<typename T>inline Sww operator>>(const T a) { w(a); return{}; }
	}out;
}using fastIO::in; using fastIO::out;
#undef ds
#define eout cerr

namespace Maths {
	const bool __is_P[] = { 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1 };
	inline bool IP1(const int a) { if (a <= 29)return __is_P[a]; if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0)return 0; for (int i = 6;; i += 6) { if (((i + 1) * (i + 1)) > a)return 1; if (a % (i + 1) == 0)return 0; if (((i + 5) * (i + 5)) > a)return 1; if (a % (i + 5) == 0)return 0; } }
#define very_fast_times(a,b,m) (c=(unsigned int)a*b-(unsigned int)((long double)a/m*b+0.5L)*m,c<m?c:m+c)
	inline int power(int a, int b, const int mod = -1) { unsigned int c; int ans = 1; if (mod == -1) { for (; b;) { if (b & 1)ans *= a; b >>= 1; a *= a; }return ans; }for (; b;) { if (b & 1)ans = very_fast_times(ans, a, mod); b >>= 1; a = very_fast_times(a, a, mod); }return ans; }
	const int Suk[] = { 2,325,9375,28178,450775,9780504,1795265022 };
	inline bool chk(const int n, int a, int b, int x) { if (x >= n) return 1; unsigned int c; int v = power(x, a, n); if (v == 1)return 1; int j = 1; while (j <= b) { if (v == n - 1)break; v = very_fast_times(v, v, n); j++; }if (j > b)return 0; return 1; }
	inline bool IP(int n) { if (n < 3 || n % 2 == 0)return n == 2; if (n <= 1e6) { return IP1(n); } else { int a = n - 1, b = 0; while (a % 2 == 0)a >>= 1, b++; for (auto k : Suk)if (!chk(n, a, b, k))return 0; return 1; } }
} using Maths::power;
using Maths::IP;

//#define BIT Binary_Indexed_Tree 
#ifdef BIT
namespace BIT {//下标从1开始
	struct ds {//打死要记住初始化 ds.n
#define maxn 100005
		int c0[maxn], c1[maxn], n;
		inline void Add(int* c, int p, int v) { for (; p <= n; p += p & -p)c[p] += v; }
		inline int Sum(int* c, int p) { int t = 0; for (; p; p -= p & -p)t += c[p]; return t; }
		inline int sum(int l, int r) { return Sum(c0, r) * r - Sum(c1, r) - Sum(c0, l - 1) * (l - 1) + Sum(c1, l - 1); }
		inline void add(int l, int r, int v) { Add(c0, l, v); Add(c0, r + 1, -v); Add(c1, l, (l - 1) * v); Add(c1, r + 1, -r * v); }
		inline void init(int* c, int len) { int last = 0; for (int i = 1; i <= len; i++) { last = c[i] - last; Add(c0, i, last); Add(c1, i, last * (i - 1)); last = c[i]; } }
	};
#undef maxn
}using namespace BIT;
#endif

//#define ST Sparse_Table
#ifdef ST
namespace ST {//下标从1开始
	struct st {
#define maxn 100005
#define bq min
		int lg[maxn], f[maxn][18];
		void init(int* c, int len) { for (int i = 2; i <= len; i++)lg[i] = lg[i >> 1] + 1; for (int i = 1; i <= len; i++)f[i][0] = c[i]; for (int j = 1; (1 << j) <= len; j++) { for (int i = 1; i + (1 << j) - 1 <= len; i++)f[i][j] = bq(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); } }
		int query(int l, int r) { int j = lg[r - l + 1]; return bq(f[l][j], f[r - (1 << j) + 1][j]); }
	};
#undef maxn
#undef bq
}using namespace ST;
#endif
int n,m;
char ch[55][55];
int id[55][55];
struct node{
	int x,y,t;
	friend inline bool operator<(node a,node b){
		return a.t>b.t;
	}
};
vector<node>e[20];
int tot=0;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(int x,int y,int k){
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx<1||yy<1||xx>n||yy>m||ch[xx][yy]!='X'||id[xx][yy]!=0)continue;
		id[xx][yy]=k;
		e[k].push_back({xx,yy,0});
		dfs(xx,yy,k);
	}
}
//bfs
bool is[55][55];
bool vis[55][55];
int Y[25][25];
//dp
int f[1<<15|111][25];
signed main() {
	in>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			in>>ch[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if((id[i][j]==0)&&ch[i][j]=='X'){
				id[i][j]=++tot;
				e[tot].push_back({i,j,0});
				dfs(i,j,tot);
			}
		}
	}
	if(tot==1){
		out<<"0";
		return 0;
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			out<<id[i][j]<<" ";
//		}
//		out<<'\n';
//	}
	for(int i=1;i<=tot;i++){
		for(int j=i+1;j<=tot;j++){
			priority_queue<node>q;
			memset(is,0,sizeof(is));
			memset(vis,0,sizeof(vis));
			for(auto k:e[i]){
				q.push(k);
				vis[k.x][k.y]=1;
			}
			for(auto k:e[j])is[k.x][k.y]=1;
			int ans=1e15;
			for(;!q.empty();){
				auto T=q.top();q.pop();
				int x=T.x,y=T.y,t=T.t;
				if(is[x][y]){
					ans=t;
					break;
				}
				for(int k=0;k<4;k++){
					int xx=x+dx[k],yy=y+dy[k];
					if(xx<1||yy<1||xx>n||yy>m||ch[xx][yy]=='.'||id[xx][yy]==i||vis[xx][yy])continue;
					vis[xx][yy]=1;
					q.push({xx,yy,t+(ch[xx][yy]=='S'?1:0)});
				}
			}
			Y[i][j]=Y[j][i]=ans;
		}
	}
//	for(int i=1;i<=tot;i++){
//		for(int j=1;j<=tot;j++){
//			out<<Y[i][j]<<" ";
//		}
//		out<<'\n';
//	}
	memset(f,0x3f,sizeof(f));
	memset(f[0],0,sizeof(f[0]));
	for(int i=1;i<(1<<tot);i++){
		for(int j=0;j<tot;j++){
			if(i&(1<<j)){
				for(int k=0;k<tot;k++){
					f[i][j]=min(f[i][j],f[i^(1<<j)][k]+Y[j+1][k+1]);
				}
			}
		}
	}
	int ans=1e15;
	for(int i=0;i<tot;i++){
		ans=min(ans,f[(1<<tot)-1][i]);
	}
	out<<ans<<'\n';
	return 0;
}
```
[提交记录](https://www.luogu.com.cn/record/216653633)

正在渲染内容...