UVa 10944 Nuts for nuts.cpp

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 9999999
struct Point{
    int x, y;
}point[20];         // point[0] is Larry
int num;            // num of nuts
int dis[20][20];
int dp[20][1<<16];

int main()
{
    int x, y;
    char line[30];
    while (scanf("%d %d", &x, &y) != EOF) {
        // Input
        num = 0;
        for (int i = 0; i < x; ++i) {
            scanf("%s", line);
            for (int j = 0; j < y; ++j)
                if (line[j] == '#') point[++num] = {i, j};
                else if (line[j] == 'L') point[0] = {i, j};
        }

        // Initial
        for (int i = 0; i <= num; ++i)
            for (int j = 0; j <= num; ++j)
                dis[i][j] = max(abs(point[i].x - point[j].x), abs(point[i].y - point[j].y));

        int maxz = (1 << num) - 1;  // 所有堅果被選完的時候的最終狀態(111...111)

        for (int i = 0; i <= num; ++i)
            for (int j = 0; j <= maxz; ++j) dp[i][j] = INF;

        for (int i = 1; i <= num; ++i) dp[i][1<<(i-1)] = dis[0][i];

        // dynamic programming
        for (int i = 0; i < maxz; ++i)
            for (int j = 1; j <= num; ++j)
                if (i & (1<<(j-1)))
                    for (int k = 1; k <= num; ++k)
                        if (!(i & (1<<(k-1))))
                            dp[k][i + (1<<(k-1))] = min(dp[k][i + (1<<(k-1))], dp[j][i] + dis[j][k]);

        // find the minimum route and output the ans
        int ans = INF;
        for (int i = 1; i <= num; ++i)
            ans = min(ans, dp[i][maxz] + dis[i][0]); // 加dis是因為要走回原點
        if (ans == INF) puts("0");  // when num is 0, the ans is INF
        else printf("%d\n", ans);
    }
}