Tirp（状压DP）

Description

有一个N*N的迷宫，其中有一些宝藏，现在，小A要从入口(1,1)出发，到达出口（N，N），每次，小A只能从当前的格子走到上下左右四个格子，为了不空手而归，小A决定要拿到所以的宝藏。请问，他最少要走多少步，才能拿到宝藏？

Input Format

第一行：一个整数N，表示迷宫的大小。

第二到第（N+1）行，每行有N个字符，代表迷宫的情况，其中‘0’代表路径，‘1’代表墙面，‘2’代表宝藏

Output Format

一行，一个整数，表示最少步数，或者输出No Solution，表示无法取到所以宝藏

Sample Input

011

020

110

Sample Output

Hint

100%，N<=30,宝藏个数<=13

Solution

首先，宝藏个数<=13，自然想到状压DP，用二进制数表示状态，‘1’代表这个宝藏去过了，‘0’代表没有，

那么可以用F[i][S]表示状态为S时，且位于第i个宝藏的最短步数。

那么容易得到方程F[i][S]=min{F[k][S^(1<<(i-1))]+dis[i][k]},其中1<=k<=宝藏个数，dis[i][k]表示第i个宝藏到第k个宝藏的最少步数

那么最后答案就为min{F[i][(1<<m)-1]+toEnd[i]},其中toEnd[i]表示从宝藏i到点（N ,N )的最少步数.

dis数组和toEnd数组可以用bfs预处理得到，细节也不少，当无法到达终点或有至少一个宝藏拿不到就是无解的情况，而且要特判没有宝藏时直接输出到终点的距离

当初挂了好几次，主要有以下几点原因：

记忆化时tmp忘记初始化为INF，导致答案都为-1
没有考虑没有宝藏的情况（m==0)
没有考虑到不了终点的情况
方程原来写成转移到DP(i, S ^ (1 << (i - 1))，应该是'(p-1)'
读入时临时字符串数组开小，导致RE

Code

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

const int dx[4] = {0, 0, 1, -1};

const int dy[4] = {1, -1, 0, 0};

struct point {

	point(int a, int b) {x = a, y = b;}

	int x, y;

};

struct info {

	int x, y;

} bag[32];

int n, a[32][32], m, f[32][1 << 16], dis[32][32], toEnd[32], toBag[32];

int d[32][32];

bool vis[32][32];

queue<point> q;

bool flag;

void bfs(int k, int sx, int sy) {

	memset(vis, 0, sizeof(vis));

	memset(d, -1, sizeof(d));

	d[sx][sy] = 0;

	while (!q.empty()) q.pop();

	q.push(point(sx, sy));

	vis[sx][sy] = 1;

	while (!q.empty()) {

		point u = q.front();

		int x = u.x, y = u.y;

		q.pop();

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

			int nx = x + dx[i], ny = y + dy[i];

			if (nx <= 0 || ny <= 0 || nx > n || ny > n || vis[nx][ny] || a[nx][ny]) continue;

			vis[nx][ny] = 1;

			d[nx][ny] = d[x][y] + 1;

			q.push(point(nx, ny));

		}

	}

	for (int i = k + 1; i <= m; ++i) {

		int x = bag[i].x, y = bag[i].y;

		if (d[x][y] == -1) {

			if (k == 0) flag = 1;

			continue;

		}

		if (k == 0) toBag[i] = d[x][y];

		else dis[k][i] = dis[i][k] = d[x][y];

	}

	if (d[n][n] == -1) flag = 1;

	toEnd[k] = d[n][n];

}

int DP(int p, int S) {

	int &tmp = f[p][S];

	if (tmp != -1) return tmp;

	tmp = (int)1e9;

	for (int i = 1; i <= m; ++i) {

		if (i == p) continue;

		if (!((1 << (i - 1))&S)) continue;

		tmp = min(tmp, DP(i, S ^ (1 << (p - 1))) + dis[i][p]);

	}

	return tmp;

}

int main() {

	scanf("%d", &n);

	memset(dis, 0x3f, sizeof(dis));

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

		char s[32];

		scanf("%s\n", s);

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

			a[i][j + 1] = s[j] - '0';

			if (a[i][j + 1] == 2) {

				a[i][j + 1] = 0;

				bag[++m].x = i;

				bag[m].y = j + 1;

			}

		}

	}

	bfs(0, 1, 1);

	if (flag) {

		printf("No Solution\n");

		return 0;

	}

	for (int i = 1; i <= m; ++i)

		bfs(i, bag[i].x, bag[i].y);

	int Ans = (int)1e9;

	memset(f, -1, sizeof(f));

	for (int i = 1; i <= m; ++i)

		f[i][1 << (i - 1)] = toBag[i];

	for (int i = 1; i <= m; ++i)

		Ans = min(Ans, DP(i, (1 << m) - 1) + toEnd[i]);

	if (m == 0) Ans = toEnd[0];

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

	return 0;

}