首页 > 代码库 > HDU 3681 Prison Break floyd+状压+二分
HDU 3681 Prison Break floyd+状压+二分
题目链接:点击打开链接
题意:
给定n*m的矩阵:
F:起点(有且仅有一个)
D:坏点(不能走到这个点)
G:能量池(走到这个点可以选择使用这个点的能量池,把电池充满,也可以暂时不用,只能使用一次)
Y:目标点
问:
遍历所有Y点需要最小的电池容量是多少。
开始电池满电,每走一步消耗一格电。
Y+G的个数<=15. n,m<=15
思路:状压YG,前面几位表示Y,后面几位表示G。
先跑个floyd,然后二分电池容量,状压dp判可行
#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <cstring> #include <cmath> using namespace std; const int inf = 5500; const int N = 15; struct node{ int x, y; node(int a=0, int b=0):x(a),y(b){} }Y[N], G[N], P[N+1], F; int ynum, gnum, dp[1<<N][15]; int dis[N][N][N][N], step[4][2] = {0,1, 0,-1, 1,0, -1,0}; int n, m; char mp[N+10][N+10]; void bfs(int x, int y){ for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) dis[x][y][i][j] = inf; dis[x][y][x][y] = 0; queue<int> qx, qy; qx.push(x); qy.push(y); while(!qx.empty()){ int ux = qx.front(); qx.pop(); int uy = qy.front(); qy.pop(); for(int i = 0; i < 4; i++) { int vx = step[i][0] + ux, vy = step[i][1] + uy; if(false == (0<=vx && vx <n && 0<=vy && vy<m) || mp[vx][vy] == 'D') continue; if(dis[x][y][vx][vy] == inf) { dis[x][y][vx][vy] = dis[x][y][ux][uy]+1; qx.push(vx); qy.push(vy); } } } } void floyd(){ for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(mp[i][j]!='D') bfs(i,j); } bool ok(int power){ memset(dp, -1, sizeof dp); queue<int> State, End; for(int i = 0; i < ynum; i++) if(power - dis[F.x][F.y][Y[i].x][Y[i].y] >= 0) { dp[1<<i][i] = power - dis[F.x][F.y][Y[i].x][Y[i].y]; State.push(1<<i); End.push(i); } for(int i = 0; i < gnum; i++) if(power - dis[F.x][F.y][G[i].x][G[i].y] >= 0) { dp[1<<(i+ynum)][i+ynum] = power; State.push(1<<(i+ynum)); End.push(i+ynum); } while(!State.empty()) { int s = State.front(); State.pop(); int e = End.front(); End.pop(); if((s & ((1<<ynum)-1)) >= ((1<<ynum)-1))return true; for(int i = 0; i < ynum +gnum; i++) { if((s&(1<<i)) || dp[s][e] - dis[P[e].x][P[e].y][P[i].x][P[i].y] < 0)continue; if(dp[s|(1<<i)][i] == -1) { State.push(s|(1<<i)); End.push(i); } if(i<ynum) dp[s|(1<<i)][i] = max(dp[s|(1<<i)][i], dp[s][e] - dis[P[e].x][P[e].y][P[i].x][P[i].y]); else dp[s|(1<<i)][i] = power; } } return false; } void input(){ ynum = gnum = 0; for(int i = 0; i < n; i++) { scanf("%s", mp[i]); for(int j = 0; j < m; j++) { if(mp[i][j] == 'F') F = node(i,j); else if(mp[i][j] == 'Y') Y[ynum++] = node(i,j); else if(mp[i][j] == 'G') G[gnum++] = node(i,j); } } for(int i = 0; i < ynum; i++) P[i] = Y[i]; for(int i = ynum; i < ynum+gnum; i++) P[i] = G[i-ynum]; } int main(){ while(cin>>n>>m, n+m){ input(); if(ynum == 0){puts("0");continue;} floyd(); int ans = inf, l = 0, r = inf; while(l <= r){ int mid = (l+r)>>1; if(ok(mid)) r = mid-1, ans = min(ans, mid); else l = mid+1; } if(ans == inf) ans = -1; cout<<ans<<endl; } return 0; } /* 1 2 FY 1 4 FYGY */
HDU 3681 Prison Break floyd+状压+二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。