[UVA] 10944 - Nuts for nuts..

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10944 - Nuts for nuts..
Source            : Light Online Judge
Category          : Dynamic Programing
Algorithm         : Bitmask DP, TSP
Verdict           : Accepted

1. #include "bits/stdc++.h"  
2.   
3. using namespace std;  
4.   
5. #define pii           pair <int, int>  
6.   
7. static const int maxn = 20 + 2;  
8.   
9. int row, column;  
10. char grid[maxn][maxn];  
11. pii ind[maxn];  
12.   
13. int getDis(int p, int q)  
14. {  
15.       int r = abs(ind[p].first - ind[q].first);  
16.       int c = abs(ind[p].second - ind[q].second);  
17.       return max(r, c);  
18. }  
19.   
20. int getDis2(pii a, int p)  
21. {  
22.       int r = abs(a.first - ind[p].first);  
23.       int c = abs(a.second - ind[p].second);  
24.       return max(r, c);  
25. }  
26.   
27. int dp[15][65540];  
28. bool memoize[15][65540];  
29. int n;  
30. pii L;  
31.   
32. int TSP(int now = 0, int mask = 0)  
33. {  
34.       if (__builtin_popcount(mask) == n) return dp[now][mask] = getDis2(L, now);  
35.       int &ret = dp[now][mask];  
36.       bool &mem = memoize[now][mask];  
37.       if (mem) return ret;  
38.       mem = 1;  
39.       int ans = INT_MAX;  
40.       for (int nxt = 0; nxt < n; nxt++)  
41.       {  
42.             bool can = (bool)(mask & (1 << nxt));  
43.             if (!can)  
44.             {  
45.                   int go = getDis(now, nxt) + TSP(nxt, mask | (1 << nxt));  
46.                   ans = min(ans, go);  
47.             }  
48.       }  
49.       return ret = ans;  
50. }  
51.   
52. int main()  
53. {  
54.       ios_base::sync_with_stdio(false);  
55.       cin.tie(nullptr);  
56.       #ifndef ONLINE_JUDGE  
57.             freopen("in.txt", "r", stdin);  
58.       #endif // ONLINE_JUDGE  
59.       while (cin >> row >> column)  
60.       {  
61.             n = 0;  
62.             for (int i = 1; i <= row; i++)  
63.             {  
64.                   string s;  
65.                   cin >> s;  
66.                   for (int j = 1; j <= column; j++)  
67.                   {  
68.                         if (s[j-1] == 'L') L = pii(i, j);  
69.                         else if (s[j-1] == '#') ind[n++] = pii(i, j);  
70.                   }  
71.             }  
72.             if (n == 0)  
73.             {  
74.                   cout << 0 << "\n";  
75.                   continue;  
76.             }  
77.             memset(memoize, 0, sizeof memoize);  
78.             int ans = INT_MAX;  
79.             for (int i = 0; i < n; i++)  
80.             {  
81.                   int add = getDis2(L, i);  
82.                   int mask = 0;  
83.                   int tsp = TSP(i, mask | (1 << i)) + add;  
84.                   ans = min(ans, tsp);  
85.             }  
86.             cout << ans << "\n";  
87.       }  
88. }