HDU 5067 Harry And Dig Machine

思路：因为点才10个，在加上一个起点，处理出每一个点之间的曼哈顿距离，然后用状压dp搞，状态表示为：

dp[i][s]，表示在i位置。走过的点集合为s的最小代价

代码：

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int N = 15;

int n, m;

struct Point {

	int x, y;

	Point() {}

	Point(int x, int y) {

		this->x = x;

		this->y = y;

	}

} p[N];

int pn;

int g[N][N];

int dp[N][(1<<13) + 5];

int dis(Point a, Point b) {

	return abs(a.x - b.x) + abs(a.y - b.y);

}

const int INF = 0x3f3f3f3f;

int main() {

	while (~scanf("%d%d", &n, &m)) {

		pn = 0;

		int a;

		int flag = 0;

		int zero;

		for (int i = 0; i < n; i++) {

			for (int j = 0; j < m; j++) {

				scanf("%d", &a);

				if (a) {

					p[pn++] = Point(i, j);

					if (i == 0 && j == 0) {

						flag = 1;

						zero = pn - 1;

					}

				}

			}

		}

		if (!flag) {

			zero = pn;

			p[pn++] = Point(0, 0);

		}

		for (int i = 0; i < pn; i++) {

			for (int j = i; j < pn; j++) {

				g[i][j] = g[j][i] = dis(p[i], p[j]);

			}

		}

		for (int i = 0; i < pn; i++)

			for (int j = 0; j < (1<<pn); j++)

				dp[i][j] = INF;

		dp[zero][0] = 0;

		dp[zero][(1<<zero)] = 0;

		int ss = (1<<pn);

		for (int i = 0; i < ss; i++) {

			for (int j = 0; j < pn; j++) {

				if (i&(1<<j)) {

					for (int k = 0; k < pn; k++) {

						if (i&(1<<k)) {

							dp[j][i] = min(dp[j][i], dp[k][i^(1<<j)] + g[j][k]);

						}

					}

				}

			}

		}

		int ans = INF;

		for (int i = 0; i < pn; i++)

			ans = min(ans, dp[i][(1<<pn) - 1] + g[zero][i]);

		printf("%d\n", ans);

	}

	return 0;

}