Advertisement
omar-alhelo

CLEANRBT

Sep 15th, 2018
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ld long double
  5. #define VI vector<int>
  6. #define _f front
  7. #define _b back
  8. #define _pb push_back
  9. #define _pf push_front
  10. #define _Pb pop_back
  11. #define _Pf pop_front
  12. #define _all(v) v.begin(), v.end()
  13. #define II pair<int,int>
  14. #define III pair<int, II>
  15. #define F first
  16. #define S second
  17. #define _mp make_pair
  18. #define LINE  putc('\n', stdout)
  19. #define SPACE putc(' ' , stdout)
  20. #define TAB   putc('\t', stdout)
  21. #define _out(_)            printf("%i",_)
  22. #define __out(_,__)        printf("%i %i",_,__)
  23. #define ___out(_,__,___)   printf("%i %i %i",_,__,___)
  24. #define _outLL(_)          printf("%I64d",_)
  25. #define __outLL(_,__)      printf("%I64d %I64d",_,__)
  26. #define ___outLL(_,__,___) printf("%I64d %I64d %I64d",_,__,___)
  27. #define _in(_)             scanf("%i", &_)
  28. #define __in(_,__)         scanf("%i%i",&_,&__)
  29. #define ___in(_,__,___)    scanf("%i%i%i",&_,&__,&___)
  30. #define _inLL(_)           scanf("%I64d", &_)
  31. #define __inLL(_,__)       scanf("%I64d%I64d",&_,&__)
  32. #define ___inLL(_,__,___)  scanf("%I64d%I64d%I64d",&_,&__,&___)
  33. #define _debug(_) printf("-----------> Debuging : %i\n",_ );
  34. #define _for(i, n) for(int i=0 ; i<n ; i++)
  35. #define _rof(i, n) for(int i=n ; i-- ;    )
  36. #define rm_imp(d, p) (round(d*p)/p)
  37. #define INF 2e8
  38. char A[33*33];
  39. VI v;
  40. int w, h, n, dist[14][14], D[33*33];
  41. int memo[14][1<<14];
  42. int TSP(int p, int mask)
  43. {
  44.   if(mask==(1<<n)-1)    return 0;
  45.   if(memo[p][mask]!=-1) return memo[p][mask];
  46.   int ans = INF;
  47.   _rof(i, n)
  48.     if(!(mask&1<<i))
  49.       ans= min(ans, TSP(i, mask|1<<i) + dist[p][i]);
  50.   return memo[p][mask]=ans;
  51. }
  52. int generate_D(int source)
  53. {
  54.   int dir[] = {-1, w, +1 , -w};
  55.   deque<int> dq;
  56.   memset(D, -1, sizeof D);
  57.   D[source]=0;
  58.   dq._pf(source);
  59.   while(!dq.empty())
  60.   {
  61.     int s = dq._f();
  62.     dq._Pf();
  63.     _for(j, 4)
  64.     {
  65.       int d = s + dir[j] ;
  66.       if(D[d]==-1 && A[d]!='x')
  67.         D[d]=D[s]+1 , dq._pb(d);
  68.     }
  69.   }
  70. }
  71. int main()
  72. {
  73.   repeate :
  74.   while(__in(w,h), w)
  75.   {
  76.     memset(memo, -1, sizeof memo);
  77.     v.clear();
  78.     char *ptr = A;
  79.     _for(i, w+2) *ptr++='x';
  80.     _for(i, h) { *ptr++='x'; scanf("%s", ptr); ptr+=w; *ptr++='x'; }
  81.     _for(i, w+2) *ptr++='x';
  82.     *ptr=0;
  83.     w+=2; h+=2;
  84.     v._pb(strstr(A, "o")-A);
  85.     ptr=A; ptr--;
  86.     while(ptr=strstr(ptr+1, "*")) v._pb(ptr-A);
  87.     n = v.size();
  88.     _for(i, n){
  89.       generate_D(v[i]);
  90.       _for(j, n){
  91.         if(D[v[j]]==-1) {_out(-1);LINE;goto repeate;}
  92.         dist[i][j]=D[v[j]];
  93.       }
  94.     }
  95.     _out(TSP(0, 1));LINE;
  96.   }
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement