首页 > 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. 神经广告 有没有管理的 竟然插这种广告 搞清楚我们是来看漫画的不是看这种的 漫画好看必定有人欣赏 不用弄这种来吸引人或是作于其他用途 真是无聊 东西刚出来的时候总会标榜自己有多好 之后就跟其他的东西一样慢慢参些不好的东西进去 一点新意也没有

  2. 神经广告 有没有管理的 竟然插这种广告 搞清楚我们是来看漫画的不是看这种的 漫画好看必定有人欣赏 不用弄这种来吸引人或是作于其他用途 真是无聊 东西刚出来的时候总会标榜自己有多好 之后就跟其他的东西一样慢慢参些不好的东西进去 一点新意也没有

  3. 神经广告 有没有管理的 竟然插这种广告 搞清楚我们是来看漫画的不是看这种的 漫画好看必定有人欣赏 不用弄这种来吸引人或是作于其他用途 真是无聊 东西刚出来的时候总会标榜自己有多好 之后就跟其他的东西一样慢慢参些不好的东西进去 一点新意也没有

  4. 神经广告 有没有管理的 竟然插这种广告 搞清楚我们是来看漫画的不是看这种的 漫画好看必定有人欣赏 不用弄这种来吸引人或是作于其他用途 真是无聊 东西刚出来的时候总会标榜自己有多好 之后就跟其他的东西一样慢慢参些不好的东西进去 一点新意也没有

  5. 神经广告 有没有管理的 竟然插这种广告 搞清楚我们是来看漫画的不是看这种的 漫画好看必定有人欣赏 不用弄这种来吸引人或是作于其他用途 真是无聊 东西刚出来的时候总会标榜自己有多好 之后就跟其他的东西一样慢慢参些不好的东西进去 一点新意也没有

  6. 神经广告 有没有管理的 竟然插这种广告 搞清楚我们是来看漫画的不是看这种的 漫画好看必定有人欣赏 不用弄这种来吸引人或是作于其他用途 真是无聊 东西刚出来的时候总会标榜自己有多好 之后就跟其他的东西一样慢慢参些不好的东西进去 一点新意也没有

  7. 神经广告 有没有管理的 竟然插这种广告 搞清楚我们是来看漫画的不是看这种的 漫画好看必定有人欣赏 不用弄这种来吸引人或是作于其他用途 真是无聊 东西刚出来的时候总会标榜自己有多好 之后就跟其他的东西一样慢慢参些不好的东西进去 一点新意也没有

  8. 神经广告 有没有管理的 竟然插这种广告 搞清楚我们是来看漫画的不是看这种的 漫画好看必定有人欣赏 不用弄这种来吸引人或是作于其他用途 真是无聊 东西刚出来的时候总会标榜自己有多好 之后就跟其他的东西一样慢慢参些不好的东西进去 一点新意也没有

  9. 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.

  10. 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.