https://citel.bjtu.edu.cn/acm/oj/problem/1846
1846. Infinity的装备
时间限制 1000 ms
内存限制 64 MB
题目描述
“测试服终于下完了！” Infinity 来到了一望无际的沙漠 Miramar。
Infinity 降落到了 Los Leones 城，他在天上看到城区里有一些装备。
但是城区地形复杂、装备繁多，来回捡各种装备肯定要走不少回头路。
Infinity 想尽快搜齐所有装备，你能告诉他最快多久可以集齐所有装备吗？
Los Leones 城可以表示为一个 n×m
的矩形。
其中，
# 表示不可穿越的高墙，I 表示 Infinity 降落的位置，E 表示装备。
Infinity 一次移动可以向上下左右之一的方向移动一格，但不能到达高墙。
当 Infinity 和装备处于同一位置时，Infinity 可以（不消耗移动步数地）立即获得这个装备。
输入数据
第一行为一个整数 t (1≤t≤200)
，表示数据的组数。接下来对于每组数据：
第一行为三个整数 n,m,k (3≤n,m≤10;1≤k≤10)
，表示城市的高、宽，和装备的数量。
接下来 n
行，每行为一个长度为 m
的字符串，表示城市的布局，具体含义见题目描述。
保证城市的最外圈都是高墙。保证所有装备从初始位置可达。
输出数据
对于每组数据，输出一行：
第一行为一个整数，表示 Infinity 集齐所有装备所需最少的移动次数。
样例输入
1
5 7 2
#######
# I #
# ### #
# E#E #
#######样例输出
14样例说明
测试数据有点小问题，迷之 WA / RE / TLE 可以看一下这个链接。
http://blog.csdn.net/qwb492859377/article/details/48323443
[分析]:状压dp+dfs /网上搜一下这个有蛮多类似的题目.
[代码]:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
#define ll long long
#define sz(x) (int)(x).size()
char a[][];
int id[][];
struct node{
int r,c;
};
int dp[<<][];
int sd[];
int ed[][];
vector<node> e;
int tmpd[][];
bool safe_gets(char *S){
int n = strlen(S);
if(!gets(S)) return false;
if(n && S[n - ] =='\r') S[n - ] = ;
return true;
}
int Lowbit(int x){
return x&(-x);
}
int xx[];
int main(){
int tmp=;
for(int i=;i<;i++){
xx[tmp]=i;
tmp*=;
}
int t;
scanf("%d",&t);
while(t--){
e.clear();
node s;
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
getchar();
getchar();
for(int i=;i<=n;i++){
safe_gets(a[i]+);
for(int j=;j<=m;j++){
if(a[i][j]=='E'){
id[i][j]=sz(e);
e.pb({i,j});
}else if(a[i][j]=='I'){
s={i,j};
}
}
}
if(sz(e)!=k)return ;
memset(tmpd,,sizeof(tmpd));
tmpd[s.r][s.c]=;
queue<pair<int,int>> q;
q.push({s.r,s.c});
while(q.size()){
int r=q.front().fi,c=q.front().se;
if(a[r][c]=='E'){
sd[id[r][c]]=tmpd[r][c];
}
q.pop();
if(a[r+][c]!='#' && tmpd[r+][c]==tmpd[][]){
tmpd[r+][c]=tmpd[r][c]+;
q.push({r+,c});
}
if(a[r][c+]!='#' && tmpd[r][c+]==tmpd[][]){
tmpd[r][c+]=tmpd[r][c]+;
q.push({r,c+});
}
if(a[r-][c]!='#' && tmpd[r-][c]==tmpd[][]){
tmpd[r-][c]=tmpd[r][c]+;
q.push({r-,c});
}
if(a[r][c-]!='#' && tmpd[r][c-]==tmpd[][]){
tmpd[r][c-]=tmpd[r][c]+;
q.push({r,c-});
}
}
for(int i=;i<sz(e);i++){
memset(tmpd,,sizeof(tmpd));
tmpd[e[i].r][e[i].c]=;
q.push({e[i].r,e[i].c});
while(q.size()){
int r=q.front().fi,c=q.front().se;
if(a[r][c]=='E'){
ed[i][id[r][c]]=tmpd[r][c];
}
q.pop();
if(a[r+][c]!='#' && tmpd[r+][c]==tmpd[][]){
tmpd[r+][c]=tmpd[r][c]+;
q.push({r+,c});
}
if(a[r][c+]!='#' && tmpd[r][c+]==tmpd[][]){
tmpd[r][c+]=tmpd[r][c]+;
q.push({r,c+});
}
if(a[r-][c]!='#' && tmpd[r-][c]==tmpd[][]){
tmpd[r-][c]=tmpd[r][c]+;
q.push({r-,c});
}
if(a[r][c-]!='#' && tmpd[r][c-]==tmpd[][]){
tmpd[r][c-]=tmpd[r][c]+;
q.push({r,c-});
}
}
}
int res=1e9;
memset(dp,,sizeof(dp));
for(int i=;i<k;i++){
dp[<<i][i]=sd[i];
if(k==)res=sd[i];
}
int up=(<<k);
for(int j=;j<=k;j++){
for(int mask = (<<j)-;mask<up;){
vector<int> out,in;
for(int i=;i<k;i++){
if(mask&(<<i)){
in.pb(i);
}
else out.pb(i);
}
for(int i=;i<sz(in);i++){
for(int j=;j<sz(out);j++){
dp[mask|(<<out[j])][out[j]]=min(dp[mask|(<<out[j])][out[j]],dp[mask][in[i]]+ed[in[i]][out[j]]);
}
}
int tmp=mask & -mask;
mask = (mask + tmp) | (((mask^(mask+tmp))>>)/tmp);
}
}
for(int i=;i<k;i++)res=min(dp[up-][i],res);
printf("%d\n",res);
}
return ;
}