HDU_3681
由于Y和G加起来不到15个，那么可以预先将F、Y、G之间的最短路处理出来，然后化归成TSP问题来做。
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define MAXD 20 int N, M, dis[MAXD][MAXD], g[MAXD][MAXD], mark, Y, G, sx, sy, vis[MAXD][MAXD]; int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; char b[MAXD][MAXD]; int f[1 << 15 | 10][MAXD]; void init() {int i, j;Y = 1;for(i = 1; i <= N; i ++){scanf("%s", b[i] + 1);for(j = 1; j <= M; j ++){if(b[i][j] == 'F') g[i][j] = 0, sx = i, sy = j;else if(b[i][j] == 'S') g[i][j] = -1;else if(b[i][j] == 'Y') g[i][j] = Y ++;else if(b[i][j] == 'D') g[i][j] = -2;}}mark = (1 << Y) - 2, G = Y;for(i = 1; i <= N; i ++)for(j = 1; j <= M; j ++)if(b[i][j] == 'G') g[i][j] = G ++; } inline int inside(int x, int y) {return x >= 1 && x <= N && y >= 1 && y <= M; } void dfs(int x, int y) {int i, nx, ny;vis[x][y] = 1;for(i = 0; i < 4; i ++){nx = x + dx[i], ny = y + dy[i];if(inside(nx, ny) && !vis[nx][ny] && g[nx][ny] != -2) dfs(nx, ny);} } int check() {int i, j;memset(vis, 0, sizeof(vis));dfs(sx, sy);for(i = 1; i <= N; i ++)for(j = 1; j <= M; j ++)if(b[i][j] == 'Y' && !vis[i][j]) return 0;return 1; } void bfs(int sx, int sy) {int i, j, x, y, nx, ny, id = g[sx][sy];memset(vis, -1, sizeof(vis));std::queue <int> q;vis[sx][sy] = 0;q.push(sx * (M + 1) + sy);while(!q.empty()){x = q.front() / (M + 1), y = q.front() % (M + 1), q.pop();if(g[x][y] >= 0) dis[id][g[x][y]] = vis[x][y];for(i = 0; i < 4; i ++){nx = x + dx[i], ny = y + dy[i];if(inside(nx, ny) && vis[nx][ny] == -1 && g[nx][ny] != -2)vis[nx][ny] = vis[x][y] + 1, q.push(nx * (M + 1) + ny);}} } int dp(int limit) {int i, j, k;memset(f, -1, sizeof(f));f[1][0] = limit;for(i = 1; i < (1 << G); i ++)for(j = 0; j < G; j ++){if(f[i][j] == -1) continue;if((i & mark) == mark) return 1;for(k = 0; k < G; k ++)if((i & 1 << k) == 0 && f[i][j] >= dis[j][k]){if(k >= Y) f[i | 1 << k][k] = limit;else f[i | 1 << k][k] = std::max(f[i | 1 << k][k], f[i][j] - dis[j][k]);}}return 0; } void solve() {int i, j;if(Y == 1){printf("0\n");return ;}if(!check()){printf("-1\n");return ;}memset(dis, 0x3f, sizeof(dis));for(i = 1; i <= N; i ++)for(j = 1; j <= M; j ++)if(g[i][j] >= 0) bfs(i, j);int min = 0, max = 1000, mid;for(;;){mid = min + max + 1 >> 1;if(mid == max) break;if(dp(mid)) max = mid;else min = mid;}printf("%d\n", mid); } int main() {while(scanf("%d%d", &N, &M), N || M){init();solve();}return 0; }