SHARE
TWEET

Untitled

a guest Jul 16th, 2018 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  ID: bradyawn
  3.  PROG: contest
  4.  LANG: C++11
  5.  */
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <vector>
  12. #include <deque>
  13. #include <string>
  14. #include <cmath>
  15. #include <map>
  16. #include <unordered_map>
  17. #include <utility>
  18. #include <set>
  19. #include <unordered_set>
  20. #include <ctime>
  21. #include <queue>
  22. #include <stack>
  23. #include <bitset>
  24. #include <random>
  25. #include <cstring>
  26. #include <complex>
  27.  
  28. using namespace std;
  29.  
  30. typedef long long ll;
  31. typedef pair<int,int> i2;
  32. typedef pair<ll,ll> ll2;
  33.  
  34. int r,c,n;
  35.  
  36. struct S
  37. {
  38.     int row;
  39.     int col;
  40.     int dist;
  41. };
  42.  
  43. deque<S> d;
  44.  
  45. char grid[51][51];
  46. char sGrid[51][51];
  47. int ans[51][51];
  48.  
  49. int island[16][16];
  50.  
  51. void add(int i, int j, int prevD)
  52. {
  53.     if (!(i >= 1 && i <= r)) return;
  54.     if (!(j >= 1 && j <= c)) return;
  55.     if (grid[i][j] == '.') return;
  56.     if (grid[i][j] == 'X') d.push_front({i,j,prevD});
  57.     if (grid[i][j] == 'S') d.push_back({i,j,prevD+1});
  58. }
  59.  
  60. void fix()
  61. {
  62.     d.clear();
  63.     for (int i = 1; i <= r; i++)
  64.         for (int j = 1; j <= c; j++) grid[i][j] = sGrid[i][j];
  65. }
  66.  
  67. int dfs(int i, int j) //find distance from island at i,j to fixed island
  68. {
  69.     if (!(i >= 1 && i <= r)) return 1e9;
  70.     if (!(j >= 1 && j <= c)) return 1e9;
  71.     if (grid[i][j] != 'X') return 1e9;
  72.     grid[i][j] = '.';
  73.    
  74.     int ret = ans[i][j];
  75.    
  76.     ret = min(ret, dfs(i+1, j));
  77.     ret = min(ret, dfs(i-1, j));
  78.     ret = min(ret, dfs(i, j+1));
  79.     ret = min(ret, dfs(i, j-1));
  80.    
  81.     return ret;
  82. }
  83.  
  84. void bfs(S st)
  85. {
  86.     memset(ans, 0, sizeof ans);
  87.     fix();
  88.    
  89.     d.push_front(st);
  90.    
  91.     while (!d.empty())
  92.     {
  93.         auto node = d.front(); d.pop_front();
  94.         int i = node.row;
  95.         int j = node.col;
  96.        
  97.         grid[i][j] = '.';
  98.        
  99.         ans[i][j] = node.dist;
  100.        
  101.         add(i+1, j, node.dist);
  102.         add(i-1, j, node.dist);
  103.         add(i, j+1, node.dist);
  104.         add(i, j-1, node.dist);
  105.        
  106.        
  107.     }
  108. }
  109.  
  110. /*
  111.  void prnt()
  112.  {
  113.  for (int i = 1; i <= r; i++)
  114.  for (int j = 1; j <= c; j++) outf << ans[i][j] << " \n"[j==c];
  115.  outf << '\n';
  116.  }*/
  117.  
  118. int dp[1<<16][16];
  119.  
  120. int solve(int mask, int cur)
  121. {
  122.     int ret = 1e9;
  123.     if (dp[mask][cur] != -1) return dp[mask][cur];
  124.     if (mask == ((1 << n)-1)) return 0;
  125.     for (int i = 0; i < n; i++)
  126.         if ( ((1 << i) & mask) == 0) ret = min(ret, island[cur][i]+solve(mask | (1 << i), i));
  127.     return dp[mask][cur] = ret;
  128. }
  129.  
  130. int main()
  131. {
  132.     ifstream inf("island.in");
  133.     ofstream outf("island.out");
  134.     //outf << setprecision(10);
  135.     ios::sync_with_stdio(0); inf.tie(0);
  136.    
  137.     inf >> r >> c;
  138.    
  139.     vector<S> pts; //start points
  140.    
  141.     for (int i = 1; i <= r; i++)
  142.         for (int j = 1; j <= c; j++)
  143.         {
  144.             inf >> grid[i][j];
  145.             sGrid[i][j] = grid[i][j];
  146.         }
  147.    
  148.     for (int i = 1; i <= r; i++)
  149.         for (int j = 1; j <= c; j++)
  150.         {
  151.             if (grid[i][j] == 'X') pts.push_back({i,j,0});
  152.             dfs(i,j);
  153.         }
  154.    
  155.     n = pts.size();
  156.    
  157.     for (int i = 0; i < n; i++)
  158.     {
  159.         bfs(pts[i]); fix();
  160.         for (int j = 0; j < n; j++) island[i][j] = dfs(pts[j].row, pts[j].col);
  161.     }
  162.    
  163.     memset(dp, -1, sizeof dp);
  164.    
  165.     for (int mask = (1 << n)-1; mask >= 0; mask--)
  166.         for (int cur = 0; cur < n; cur++) solve(mask, cur);
  167.    
  168.     outf << solve(0,15) << '\n';
  169.    
  170.     return 0;
  171.    
  172. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top