題目鏈接：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;
const int N = 17;
int dsx[4] = 
{1,0,-1,0};
int dsy[4] = {0,1,0,-1};
int dis[N][N][N][N];
int dp[1 << 16][16];
string map[N];
int n,m;
struct Point
{
int x;
int y;
Point(int _x = 0,int _y = 0):x(_x),y(_y){}
};
vector<Point> vecPoint;
int startId;
int yCnt = 0;
int successState;
void BFS(Point start)
{
queue<Point> que;
dis[start.x][start.y][start.x][start.y] = 0;
que.push(start);
Point cur;
Point next;
while(!que.empty())
{
cur = que.front();
que.pop();
for(int i = 0; i < 4; ++i)
{
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))
{
if((map[cur.x][cur.y] != 'D') && (dis[start.x][start.y][next.x][next.y] == -1))
{
dis[start.x][start.y][next.x][next.y] = dis[start.x][start.y][cur.x][cur.y] + 1;
que.push(next);
}
}
}
}
}
int BIT(int state,int j)
{
return ( (state & (1 << j)) >> (j) );
}
int SET(int state,int j)
{
return (state |= (1 << j));
}
bool Contain(int state,int sub)
{
return ((state&sub) == sub);
}
bool Check(int step)
{
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)
{
for(int j = 0; j < num; ++j)
{
if(dp[i][j] != -1 && BIT(i,j) != 0)
{
if(Contain(i,successState))
opt = max(opt,dp[i][j]);
for(int k = 0; k < num; ++k)
{
if(BIT(i,k) == 0)
{
int sa = SET(i,k);
if(dis[vecPoint[j].x][vecPoint[j].y][vecPoint[k].x][vecPoint[k].y] != -1)
{
int tmp = dp[i][j] - dis[vecPoint[j].x][vecPoint[j].y][vecPoint[k].x][vecPoint[k].y];
if(tmp >= 0)
{
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);
}
int BinarySlove(int low,int high)
{
int mid = 0;
int ans = 1 << 30;
while(low <= high)
{
mid = (low + high)/2;
if(Check(mid))
{
ans = min(ans,mid);
high = mid - 1;
}
else
{
low = mid + 1;
}
}
if(ans != 1 << 30)
return ans;
else
return -1;
}
void Test()
{
vecPoint.clear();
yCnt = 0;
successState = 0;
for(int i = 0; i < n; ++i)
{
cin >> map[i];
for(int j = 0; j < map[i].length(); ++j)
{
switch(map[i][j])
{
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));
}
int main()
{
while(scanf("%d %d",&n,&m) != EOF)
{
if(n == 0 || m == 0)
break;
Test();
}
return 0;
}posted on 2010-11-10 16:54
bennycen 閱讀(776)
評論(1) 編輯 收藏 引用 所屬分類:
算法題解