九度oj1404机器人网店

时间限制：1 秒

 

内存限制：32 兆

 

特殊判题：否

 

提交：285

 

解决：55

 

题目描述：

         ID为TMao的淘宝用户前些日子在淘宝机器人网店购买了一个智能机器人oz.这个机器人不仅精致小巧，还具有很多有意思的功能。

 

比如：oz可以在迷宫里自由的上下左右走动; 并且，在不碰到障碍物的情况下，它能够以最短时间从入口处走到出口 (假设存在的话); 最智能的是，在有充电器的地方oz还可以给自己充电 (^_^)。

 

现在，TMao设计了很多种迷宫，并且在里面随意的摆了些充电器，想请你们帮他算下，这个智能机器人要多久时间可以走出去呢？

 

他做了如下假设：

 

         1.迷宫可以看作是长为w，宽为h的网格；

         2.机器人每移动一步，需要时间1s，消耗电量0.5格；

         3.机器人初始电量为满格4格；

         4.每个充电器充电次数不限 (充电时间所需时间忽略不计)，机器人可以反复经过一个地方，但是不能走到有障碍的地方,并且一旦机器人电量变为0,它就只能停下来，哪怕这个位置正好有充电器，它也没有足够的电量去执行充电操作；

         5.机器人走到迷宫出口，必须至少还有0.5格电量，否则也算没走出出口。

输入：

输入有多组测试案例，每个测试案例以如下形式输入。

 

第一行输入w,h分别表示迷宫的长和宽，当输入0 0时结束输入（w , h <= 10）。

 

接下来的h行表示迷宫的布局：-1表示该位置是障碍物, 0表示该位置什么也没有,1表示迷宫入口, 2表示迷宫出口, 3表示该位置有充电器。

 

输出：

对应每个测试案例，输出机器人oz走到出口处的时间;如果无法按要求走到出口则输出”Pity oz!”。

 

样例输入：

4 3

2 0 0 0

0 0 0 0

0 0 0 1

4 3

2 -1 0 0

-1 0 0 0

3 0 0 1

0 0

样例输出：

5

Pity oz!

 

2012年九度互动社区淘宝实习生春季招聘上机考试

 

这道题是最短路径问题，不过他加了一些限制条件。

 

就是每次到了一个新的充电地方就可以以饱满的电量继续前进。

 

所以我就先从起点开始找。

 

每次到了一个充电点且比以前的路劲更优的话就可以更新路径。

 

再把这个点继续入队列，下一次又从这一个点开始BFS搜索。

 

直到全部搜索完毕。

 

 

 

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<queue>  
using namespace std;  
int map[13][13];  
int minpath[13][13]; //用来存放从原点到这一步i，j的最小步数。  
int row,col;  
int endi,endj;  
int dir[][2] = {{-1,0},{0,-1},{1,0},{0,1}};  
struct node  
{  
    int x,y;  
    int pu;   //真正的步数  
    int p;      //电池的数字用1~7表示  
    bool operator < (const node& a)const  
    {  
        return p>a.pu;  
    }      
};      
priority_queue<node> pq;  //优先队列必不可少，  
int Min(int a,int b)  
{  
    return a>b?b:a;  
}  
void BFS(struct node no)  
{  
    queue <node> q;  
    q.push(no);  
    struct node var;  
    while(!q.empty())  
    {  
        no = q.front();  
        q.pop();  
        if(map[no.x][no.y]==2)  
            minpath[no.x][no.y] = Min(minpath[no.x][no.y],no.pu);  
        if(map[no.x][no.y]==3 && no.pu<minpath[no.x][no.y])//每次找到充电点还要判断他是否是比上一次更优  
        {  
            minpath[no.x][no.y] = no.pu;  
            var = no;  
            var.p = 0;          //每次找到一个充电点就把充电归零  
            pq.push(var);       //每次找到一个充电点就要把它入队列。。核心核心  
        }  
        for(int i=0;i<4;i++)  
        {  
            int x = no.x+dir[i][0];  
            int y = no.y+dir[i][1];  
            if(map[x][y]!=-1 && no.p<7)  //不能到7，到7就是只有0.5电量，不能进行下一步了  
            {  
                var.x = x;  
                var.y = y;  
                var.pu = no.pu+1;  
                var.p = no.p+1;  
                q.push(var);  
            }  
        }  
    }  
}      
int main()  
{  
    int i,j;  
    while(scanf("%d%d",&col,&row) && row+col!=0)  
    {  
        struct node no;  
        memset(map,-1,sizeof(map));  
        memset(minpath,0x3f,sizeof(minpath));  
        while(!pq.empty())  
            pq.pop();  
        for(i=1;i<=row;i++)  
        for(j=1;j<=col;j++)  
        {  
        scanf("%d",&map[i][j]);  
        if(map[i][j]==1)  
        {  
        no.x = i;  
        no.y = j;  
        no.p = no.pu = 0;  
        pq.push(no);  
        }  
        if(map[i][j]==2)  
        {  
            endi = i;  
            endj = j;  
        }  
        }  
        while(!pq.empty())    
        {  
            no = pq.top();  
            pq.pop();  
            BFS(no);     
        }  
        if(minpath[endi][endj]!=minpath[0][0]) //minpath[0][0]一直没有变化，所以和它比  
        printf("%d\n",minpath[endi][endj]);  
        else  
            printf("Pity oz!\n");  
    }      
    return 0;  
}       

 

 

补充：软件开发 , C++ ,