HDU 3861 Prison Breake 狀態壓縮dp+BFS+二分答案
題意：機器人有一個初始能量x，每走到G點時可選擇充滿能量（初始能量是滿的），每走一步消耗一點能量，問當x最小為多少時，可以把所有的Y都走一遍，輸出最小的x！
注意：G點和Y點加一起最多15個
附ac代碼
#include
#include
#include
#include
using namespace std;
char map[16][16];
int dp[1<<16][16],dis[16][16];
int tot[16][2];
int cnt,first,n,m,ans;
int mark[16][16];
int dui[4][2]={0,1,0,-1,1,0,-1,0};
int min(int a,int b)
{
if(ab)
return a;
return b;
}
struct node{
int x,y,time;
}cur,next;
int bfs(int x1,int y1,int x2,int y2)
{
memset(mark,0,sizeof(mark));
queueq;
cur.x=x1;
cur.y=y1;
cur.time=0;
while(!q.empty())
q.pop();
q.push(cur);
while(!q.empty())
{
cur=q.front();
q.pop();
for(int i=0;i<4;i++)
{
next.x=cur.x+dui[i][0];
next.y=cur.y+dui[i][1];
next.time=cur.time+1;
if(map[next.x][next.y]=='D')
continue;
if(next.x>=n||next.y>=m||next.x<0||next.y<0)
continue;
if(next.x==x2&&next.y==y2)
return next.time;
if(mark[next.x][next.y])
continue;
mark[next.x][next.y]=1;
q.push(next);
}
}
return -1;
}
int fun(int kkk)
{
memset(dp,-1,sizeof(dp));
int i,j;
dp[1<
