////////////////////////////////////////////////////////////////////
/*
有一些机器人在屋子里行走,他们要在不相互碰撞的情况下完成指令,地图是矩形的,每个机器人占据一个格子的位置,我们知道机器人的初始位置和方向,以及一系列命令,命令是有序的,不会有两个命令是同时发生的。
输入
多组数据,第一行为数据的组数k
每组数据以两个整数n,m开始,表示地图的尺寸,n为W-E走向的尺寸,m为N-S走
向的尺寸 (n,m<=100)
接下来一行为两个整数为p,q (p,q<=100) , 表示p个机器人,q个命令
接下来p行描述机器人的初始信息,位置(x,y)
(1<=x<=n,1<=y<=m) ,和一个字母表示机器人初始面对的方向('N','S','E','W')
接下来q行描述指令,指令构成如下
<robot i><action><repeat>
表示机器人,动作种类,重复次数
action种类有3种
1. 'L':左转90度
2. 'R':右转90度
3. 'F':前进一个格子
重复次数不会大于100。
机器人一旦发生碰撞,则停止运行,并输出相关的错误信息。
输出
有3种:
如果第i个机器人(x=0或者y=0或者x=n+1或者y=m+1),输出 Robot i crashes
into the wall
如果i和j相撞,i是移动的那个机器人,输出 Robot i crashes into robot j
如果没有碰撞发生,输出 OK
样例输入
2
5 4
2 2
1 1 E
5 4 W
1 F 7
2 F 7
5 4
2 2
1 1 E
5 4 W
1 L 96
1 F 2
样例输出
Robot 1 crashes into the wall
OK
*/
//////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
struct robot
{
int x;
int y;
int direction;
};
struct Move
{
int num;
int turn;
int repeat;
};
int maze[102][102];
robot rbt[101];
Move move[100];
void WorkOut(int m, int n, int p, int q)
{
int i, j, s, t;
for (s = 0; s < q; s++)
{
for (t = 0; t < move[s].repeat; t++)
{
if (move[s].turn == 0)
{
switch(rbt[move[s].num].direction)
{
case 0:
i = rbt[move[s].num].x;
j = rbt[move[s].num].y - 1;
break;
case 1:
i = rbt[move[s].num].x + 1;
j = rbt[move[s].num].y;
break;
case 2:
i = rbt[move[s].num].x;
j = rbt[move[s].num].y + 1;
break;
case 3:
i = rbt[move[s].num].x - 1;
j = rbt[move[s].num].y;
break;
}
if (maze[j][i] == -1)
{
cout << "Robot " << move[s].num << " crashes into the wall" << endl;
return;
}
else if(maze[j][i] == 0)
{
maze[j][i] = move[s].num;
maze[rbt[move[s].num].y][rbt[move[s].num].x] = 0;
rbt[move[s].num].y = j;
rbt[move[s].num].x = i;
}
else
{
cout << "Robot " << move[s].num << " crashes into robot " << maze[j][i] << endl;
return;
}
}
else if (move[s].turn == 1)
{
if (rbt[move[s].num].direction == 3)
rbt[move[s].num].direction = 0;
else
rbt[move[s].num].direction += 1;
}
else
{
if (rbt[move[s].num].direction == 0)
rbt[move[s].num].direction = 3;
else
rbt[move[s].num].direction -= 1;
}
}
}
cout << "OK" << endl;
}
int main()
{
int k;
int m, n, p, q;
int i, j, s, t;
char dir;
cin >> k;
for (i = 0; i < k; i++)
{
cin >> n >> m >> p >> q;
for (s = 0; s <= m + 1; s++)//初始化地图
{
maze[s][0] = -1;
maze[s][n+1] = -1;
}
for (s = 1; s <= n; s++)
{
maze[0][s] = -1;
maze[m+1][s] = -1;
for (t = 1; t <= m; t++)
maze[t][s] = 0;
}
for (j = 1; j <= p; j++)//初始化地图和机器人位值
{
cin >> rbt[j].x >> rbt[j].y;
maze[rbt[j].y][rbt[j].x] = j;
cin >> dir;
switch(dir)
{
case 'N':
rbt[j].direction = 0;
break;
case 'E':
rbt[j].direction = 1;
break;
case 'S':
rbt[j].direction = 2;
break;
case 'W':
rbt[j].direction = 3;
break;
}
}
for (j = 0; j < q; j++)
{
cin >> move[j].num;
cin >> dir;
switch(dir)
{
case 'L':
move[j].turn = -1;
break;
case 'R':
move[j].turn = 1;
break;
case 'F':
move[j].turn = 0;
break;
}
cin >> move[j].repeat;
}
WorkOut(m, n, p, q);
}
return 0;
}
/////////////////////////////////////////////////////////////////////////////////////
/*
可以通过样例,但是提交时有错误。
*/
///////////////////////////////////////////////////////////////////////////////////
[[it] 本帖最后由 andyzhshg 于 2008-4-6 19:40 编辑 [/it]]