|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <iostream> #include <cstdio> #include <vector> #include <cstdlib> #define INF 1000 using namespace std; vector<vector<int> > dp; int dis[25][25]; struct point{ int x; int y; }; point pp[405]; int x,y; int k; string s; bool visit[25]; int location; int MX; /* int trace(int a,int dist) { visit[a]=1; bool f=false; for(int i=1;i<k;i++) { if(!visit[i]) { trace(i,dist+dis[a][i]); visit[i]=0; f=1; } } if(!f) { int tmp = dist+dis[a][location]; if(tmp<MX) MX = tmp; } return 0; } */ int tsp(int status,int src) { if(dp[status][src]!=-1) return dp[status][src]; dp[status][src] = 1e9; int mask = 1<<src; for(int i=0;i<k;i++) { if(i!=src && (status & (1<<i))) dp[status][src]= min(dp[status][src],tsp(status-mask,i)+dis[i][src]); } return dp[status][src]; } int main() { while(scanf("%d %d",&x,&y)!=EOF) { k=0; for(int i=0;i<x;i++) { cin>>s; for(int j=0;j<s.size();j++) { if(s[j]=='L') { pp[k].x = i; pp[k].y = j; location = k; k++; } else if(s[j]=='#') { pp[k].x = i; pp[k].y = j; k++; } } } for(int i=0;i<k;i++) { for(int j=0;j<k;j++) { if(i==j) dis[i][j] = 0; else { int d = abs(pp[i].x-pp[j].x); int dd = abs(pp[i].y-pp[j].y); dis[i][j] = max(d,dd); } } } /*MX = INF; ********This is backtrack algo but gets TLE****** trace(location,0); visit[location]=0; cout<<MX<<"\n"; */ dp = vector< vector< int > >(1<<k,vector<int>(k,-1)); for(int i=0;i<k;i++) dp[1<<i][i]=dis[location][i]; cout<<tsp((1<<(k))-1,location)<<"\n"; } return 0; } |