posts - 33,  comments - 33,  trackbacks - 0
题目链接: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 阅读(735) 评论(1)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理