Collecting Gold

gold.cpp

//http://lightoj.com/volume_showproblem.php?problem=1057
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

int n, m;
int gold;
int memo[(1<<17)][17];
char rill[25][25];

struct point{
    int x, y;
};

int dist(point a, point b) {
    return max(abs(a.x-b.x),abs(a.y-b.y));
}

map<int,point> ryoma; 
point init;

int dp(int mask, int last) {
    if(memo[mask][last] != -1) return memo[mask][last];
    if(mask == ((1 << gold) - 1)) return memo[mask][last] = dist(init,ryoma[last]);
    int momo = (1<<30);
    for(int i = 0; i < gold; i++) {
        if(!(mask & (1 << i))) {
            momo = min(momo,dist(ryoma[last],ryoma[i]) + dp(mask | (1 << i), i));
        }
    }
    return memo[mask][last] = momo;
}

int main() {
    int t;
    scanf("%d", &t);

for(int kase = 1; kase <= t; kase++) {
    scanf("\n");
    scanf("%d %d\n", &n, &m);
    gold = 0;
    point temp;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            scanf("%c", &rill[i][j]);
            if(rill[i][j] == 'g') {
                temp.x =  i; temp.y = j;
                ryoma[gold++] = temp;
            } else if(rill[i][j] == 'x') {
                temp.x = i; temp.y = j;
                init = temp;
            }
        } scanf("\n");
    }
    for(int i = 0; i < (1 << (gold+1)); i++) {
        for(int j = 0; j < (gold+1); j++) {
            memo[i][j] = -1;
        }
    }
    memo[0][0] = 0;
    int ans = (1 << 30);
    for(int i = 0; i < gold; i++) {
        ans = min(ans, dp((1 << i),i)+dist(init,ryoma[i]));
    }
    if(ans == (1 << 30)) ans = 0;
    printf("Case %d: %d\n", kase, ans);
}
    return 0;
}