Lightoj 1057 - Collecting Gold

http://lightoj.com/volume_showproblem.php?problem=1057

1. #include <cstdio>
2. #include <cstring>
3. #include <cstdlib>
4. #include <algorithm>
5. using namespace std;
6.  
7. typedef pair< int, int > pii;
8.  
9. char grid[20][20];
10. int dp[16][1<<16], n;
11. pii g[16];
12.  
13. inline int dist(const pii &a, const pii &b) {
14.     return max(abs(a.first - b.first), abs(a.second - b.second));
15. }
16.  
17. int solve(int u, int mask) {
18.     if(mask == (1 << n) - 1) return dist(g[u], g[0]);
19.     if(dp[u][mask] != -1) return dp[u][mask];
20.     int &ret = dp[u][mask]; ret = 0x3f3f3f3f;
21.     for(int i = 0; i < n; i++)
22.         if((mask & (1 << i)) == 0)
23.             ret = min(ret, dist(g[u], g[i]) + solve(i, mask | (1 << i)));
24.     return ret;
25. }
26.  
27. int main() {
28.     int test, cs, i, j, r, c;
29.     scanf("%d", &test);
30.     for(cs = 1; cs <= test; cs++) {
31.         scanf("%d %d", &r, &c);
32.         for(n = 1, i = 0; i < r; i++) {
33.             scanf("%s", grid[i]);
34.             for(j = 0; j < c; j++) {
35.                 if(grid[i][j] == 'x') g[0] = pii(i, j);
36.                 else if(grid[i][j] == 'g') g[n++] = pii(i, j);
37.             }
38.         }
39.         memset(dp, -1, sizeof dp);
40.         printf("Case %d: %d\n", cs, solve(0, 1));
41.     }
42.     return 0;
43. }