首页 > ACM题库 > 九度OJ > 淘宝实习生春季招聘上机考试-机器人网店
2013
11-25

淘宝实习生春季招聘上机考试-机器人网店

题目描述:
         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!
#include<queue>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int w, h, m, n, a[11][11], v[11][11][9], s[4][2] =
{
{ 1, 0 },
{ -1, 0 },
{ 0, 1 },
{ 0, -1 } };
struct tt
{
	int x, y, l, e;
};
int judge(int x, int y)
{
	if (x >= 1 && x <= h && y >= 1 && y <= w && a[x][y] != -1)
		return 1;
	return 0;
}
void bfs()
{
	tt k, t;
	int i, x, y;
	k.x = m;
	k.y = n;
	k.l = 0;
	k.e = 8;
	queue<tt> Q;
	Q.push(k);
	memset(v, 0, sizeof(v));
	v[m][n][8] = 1;
	while (!Q.empty())
	{
		k = Q.front();
		Q.pop();
		for (i = 0; i < 4; i++)
		{
			x = k.x + s[i][0];
			y = k.y + s[i][1];
			if (judge(x, y) && k.e > 1)
			{
				t.x = x;
				t.y = y;
				t.e = 8;
				t.l = k.l + 1;
				if (a[x][y] == 2)
				{
					printf("%d\n", k.l + 1);
					return;
				}
				else if (a[x][y] == 3 && !v[x][y][8])
				{
					v[x][y][8] = 1;
					Q.push(t);
				}
				else if (a[x][y] == 0 && !v[x][y][k.e - 1])
				{
					v[x][y][k.e - 1] = 1;
					t.e = k.e - 1;
					Q.push(t);
				}
			}
		}
	}
	printf("Pity oz!\n");
}
int main()
{
	int i, j;
	while (~scanf("%d%d", &w, &h))
	{
		if (!w && !h)
			return 0;
		for (i = 1; i <= h; i++)
			for (j = 1; j <= w; j++)
			{
				scanf("%d", &a[i][j]);
				if (a[i][j] == 1)
				{
					m = i;
					n = j;
				}
			}
		bfs();
	}
}

 


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.