光玉小镇(bfs建图+状压dp)

题目：光玉小镇
分析：首先将每个电线杆标号，之后bfs建图，建完图后就是道状压dp的模板题了(旅行商问题)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e12+10;
const int N=205;
typedef pair<int,int> P;
typedef struct Node{ 
   
	P point;
	int H;
}Node;
int Next[][2]={ 
   { 
   1,0},{ 
   -1,0},{ 
   0,1},{ 
   0,-1}};
int n,m,t,cnt=1;
ll dp[70000][20],d[20][20];
bool book[N][N];
char f[N][N];
map<P,int> M;
bool check(int x,int y){ 
   
	
	if(x>=1&&y>=1&&x<=n&&y<=m&&!book[x][y]&&f[x][y]!='#') return true;
	return false;
	
}
ll rec(int s,int v){ 
      //状压dp
	
	if(dp[s][v]>=0){ 
   
		return dp[s][v];
	}
	if(s==(1<<(cnt-1))-1&&v==0){ 
   
		return dp[s][v]=0;
	}
	ll res=INF;
	for(int i=0;i<cnt-1;i++){ 
   
		if(!(s>>i&1)){ 
   
			res=min(res,rec(s|1<<i,i)+d[v][i]);
		}
	}
	return dp[s][v]=res;
}
int main(){ 
   
	
	P S;
	scanf("%d %d %d",&n,&m,&t);
	for(int i=1;i<=n;i++){ 
      //标号
		scanf("%s",f[i]+1);
		for(int j=1;j<=m;j++){ 
   
			if(f[i][j]=='S') S=P(i,j),M[S]=cnt++;
			else if(f[i][j]=='T') M[P(i,j)]=cnt++;
			else M[P(i,j)]=0;
		}
	}

	
	map<P,int>::iterator it;
	fill(d[0],d[0]+20*20,INF);
	for(int i=0;i<=N;i++) d[i][i]=0; 
	for(it=M.begin();it!=M.end();it++){ 
    //bfs建图
		P temp=it->first;
		if(M[temp]==0) continue; 
		queue<Node> que;
		fill(book[0],book[0]+N*N,false);
		que.push((Node){ 
   temp,0});
		book[temp.first][temp.second]=true;
		while(!que.empty()){ 
   
			
			Node T=que.front(); que.pop();
			P U=T.point;
			for(int i=0;i<4;i++){ 
   
			 	int tx=U.first+Next[i][0];
			 	int ty=U.second+Next[i][1];
			 	if(check(tx,ty)){ 
   
			 		book[tx][ty]=true;
			 		if(M[P(tx,ty)]!=0) { 
   
			 			if(M[P(tx,ty)]!=1)
			 			d[M[temp]-1][M[P(tx,ty)]-1]=T.H+1+t;
			 			else
			 			d[M[temp]-1][M[P(tx,ty)]-1]=T.H+1;
					 }
			 		que.push((Node){ 
   P(tx,ty),T.H+1});
				}
			 }
			 	
		}
	}

	memset(dp,-1,sizeof dp);

	ll sum=rec(0,0);
	if(sum>=INF) printf("-1\n");
	else printf("%lld\n",sum);

	
	
	
	
	return 0;
}

今天的文章光玉小镇(bfs建图+状压dp)分享到此就结束了，感谢您的阅读。