题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3681题目大意:机器人从F出发,走到G可以充电,走到Y关掉开关,D不能走进,要求把所有开关关掉,且电量最少,并求出该最小电量。
题解:不错的题目,由于发现数据较小1<=n,m<=15,所以可以采用状态压缩DP解决。
算法分3步:
1.预处理,计算F、G、Y两两的距离(BFS)
2.二分法求解最少电量
3.状态压缩DP检测当前电量为s时,能否走完,dp[s][x]表示状态为s,最后到达x点,所剩余的最大电池量
代码:
#include <stdio.h>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int N = 17;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dsx[4] =
{1,0,-1,0};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dsy[4] =
{0,1,0,-1};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dis[N][N][N][N];
int dp[1 << 16][16];
string map[N];
int n,m;
struct Point
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int x;
int y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Point(int _x = 0,int _y = 0):x(_x),y(_y)
{}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
vector<Point> vecPoint;
int startId;
int yCnt = 0;
int successState;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void BFS(Point start)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
queue<Point> que;
dis[start.x][start.y][start.x][start.y] = 0;
que.push(start);
Point cur;
Point next;
while(!que.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cur = que.front();
que.pop();
for(int i = 0; i < 4; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
next.x = cur.x + dsx[i];
next.y = cur.y + dsy[i];
if((next.x >= 0 && next.x < n) && (next.y >= 0 && next.y < m))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if((map[cur.x][cur.y] != 'D') && (dis[start.x][start.y][next.x][next.y] == -1))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dis[start.x][start.y][next.x][next.y] = dis[start.x][start.y][cur.x][cur.y] + 1;
que.push(next);
}
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int BIT(int state,int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return ( (state & (1 << j)) >> (j) );
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int SET(int state,int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return (state |= (1 << j));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool Contain(int state,int sub)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return ((state&sub) == sub);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool Check(int step)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
memset(dp,-1,sizeof(dp));
dp[1<<startId][startId] = step;
int opt = -1;
int num = vecPoint.size();
for(int i = 0; i < (1 << num); ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(int j = 0; j < num; ++j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(dp[i][j] != -1 && BIT(i,j) != 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(Contain(i,successState))
opt = max(opt,dp[i][j]);
for(int k = 0; k < num; ++k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(BIT(i,k) == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int sa = SET(i,k);
if(dis[vecPoint[j].x][vecPoint[j].y][vecPoint[k].x][vecPoint[k].y] != -1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int tmp = dp[i][j] - dis[vecPoint[j].x][vecPoint[j].y][vecPoint[k].x][vecPoint[k].y];
if(tmp >= 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(dp[sa][k] == -1)
dp[sa][k] = tmp;
else if(dp[sa][k] < tmp)
dp[sa][k] = tmp;
if(map[vecPoint[k].x][vecPoint[k].y] == 'G')
dp[sa][k] = step;
}
}
}
}
}
}
}
return (opt >= 0);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int BinarySlove(int low,int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int mid = 0;
int ans = 1 << 30;
while(low <= high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
mid = (low + high)/2;
if(Check(mid))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans = min(ans,mid);
high = mid - 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
low = mid + 1;
}
}
if(ans != 1 << 30)
return ans;
else
return -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Test()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
vecPoint.clear();
yCnt = 0;
successState = 0;
for(int i = 0; i < n; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cin >> map[i];
for(int j = 0; j < map[i].length(); ++j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
switch(map[i][j])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
case 'F':
vecPoint.push_back(Point(i,j));
startId = vecPoint.size() - 1;
successState |= (1 << startId);
break;
case 'G':
vecPoint.push_back(Point(i,j));
break;
case 'Y':
++yCnt;
vecPoint.push_back(Point(i,j));
int id = vecPoint.size() - 1;
successState |= (1 << id);
break;
}
}
}
//pre
memset(dis,-1,sizeof(dis));
for(int i = 0; i < vecPoint.size(); ++i)
BFS(vecPoint[i]);
int limit = vecPoint.size() * vecPoint.size();
printf("%d\n",BinarySlove(0,limit));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while(scanf("%d %d",&n,&m) != EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(n == 0 || m == 0)
break;
Test();
}
return 0;
}
posted on 2010-11-10 16:54
bennycen 阅读(756)
评论(1) 编辑 收藏 引用 所属分类:
算法题解