HDU_3681
由于Y和G加起来不到15个，那么可以预先将F、Y、G之间的最短路处理出来，然后化归成TSP问题来做。
#include#include #include #include #define MAXD 20int 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 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;}