Preparing NOJ

驾驶卡丁车

1000ms 524288K

Description:

小Q正在设计一款2D卡丁车游戏,你的任务是帮助小Q实现其中的一部分功能。

在这款游戏中,游戏地图是一张 $$$n$$$ 行 $$$m$$$ 列的网格,从上到下依次编号为第 $$$1$$$ 行到第 $$$n$$$ 行,从左往右依次编号为第 $$$1$$$ 列到第 $$$m$$$ 列,其中第 $$$i$$$ 行第 $$$j$$$ 列的格子的坐标为 $$$(i,j)$$$,每个格子要么是可以通行的平地,要么是不可通行的障碍。

在地图上的某个平地格子处有一辆由玩家操控的卡丁车。卡丁车的移动速率为 $$$v$$$,并且一共有8种可能的朝向,分别为:

  • "上":前进一步时,将从 $$$(x,y)$$$ 移动到 $$$(x-1,y)$$$。
  • "下":前进一步时,将从 $$$(x,y)$$$ 移动到 $$$(x+1,y)$$$。
  • "左":前进一步时,将从 $$$(x,y)$$$ 移动到 $$$(x,y-1)$$$。
  • "右":前进一步时,将从 $$$(x,y)$$$ 移动到 $$$(x,y+1)$$$。
  • "左上":前进一步时,将从 $$$(x,y)$$$ 移动到 $$$(x-1,y-1)$$$。
  • "右上":前进一步时,将从 $$$(x,y)$$$ 移动到 $$$(x-1,y+1)$$$。
  • "左下":前进一步时,将从 $$$(x,y)$$$ 移动到 $$$(x+1,y-1)$$$。
  • "右下":前进一步时,将从 $$$(x,y)$$$ 移动到 $$$(x+1,y+1)$$$。

一开始卡丁车朝上位于某个平地格子处,其初始移动速率为 $$$v=0$$$。接下来玩家将依次输入 $$$q$$$ 条操作指令,每条操作指令是下列中的一种:

  • "L":卡丁车朝向往左转 $$$45$$$ 度。
  • "R":卡丁车朝向往右转 $$$45$$$ 度。
  • "U":卡丁车的速率由 $$$v$$$ 增大至 $$$v+1$$$。
  • "D":卡丁车的速率由 $$$v$$$ 减小至 $$$\max(v-1,0)$$$。

在执行完每条操作指令后,卡丁车都会沿着其朝向前进 $$$v$$$ 步,在移动结束后才会继续响应后续指令。在前进的过程中,如果某一步尝试驶入某个障碍格子或者尝试驶出地图,那么说明卡丁车发生了碰撞,它将就此结束移动,在保持朝向的同时速率 $$$v$$$ 降低为 $$$0$$$。特别要注意的是,当朝向是斜$$$45$$$度时,为了防止"穿模"现象的发生,如果卡丁车两侧都是障碍,那么卡丁车同样将被认为发生了碰撞。例如卡丁车朝向右下,现在将从 $$$(x,y)$$$ 移动到 $$$(x+1,y+1)$$$,那么如果 $$$(x+1,y)$$$ 和 $$$(x,y+1)$$$ 都是障碍,则卡丁车发生了碰撞。

请写一个程序,在执行完每条操作指令后且卡丁车完成移动之后,汇报卡丁车的坐标以及这次移动过程中是否发生了碰撞。

Input:

第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$1\leq n,m\leq 50$$$),表示地图的尺寸。

接下来 $$$n$$$ 行,第 $$$i$$$ 行包含一个长度为 $$$m$$$ 的字符串,其中第 $$$j$$$ 个字符描述格子 $$$(i,j)$$$。如果它是".",则说明 $$$(i,j)$$$ 是平地;如果它是"#",则说明 $$$(i,j)$$$ 是障碍;如果它是"*",则说明 $$$(i,j)$$$ 是平地,且卡丁车位于此。输入数据保证存在恰好一个"*"。

接下来一行包含一个正整数 $$$q$$$ ($$$1\leq q\leq 500$$$),表示指令的数量。

接下来一行包含一个长度为 $$$q$$$ 的字符串,每个字符是四种指令中的一种,依次描述每条指令。

Output:

输出 $$$q$$$ 行,第 $$$i$$$ 行输出执行完第 $$$i$$$ 条指令且卡丁车完成移动之后的相关信息。如果这一次卡丁车没有发生碰撞,那么输出"x y";如果这一次卡丁车发生了碰撞,那么输出"Crash! x y"。其中 $$$x$$$ 和 $$$y$$$ 表示卡丁车的坐标为 $$$(x,y)$$$。

Sample Input:

5 4
....
##..
..#.
.*..
....
12
URULLULLLLUD

Sample Output:

3 2
Crash! 3 2
Crash! 3 2
3 2
3 2
Crash! 3 2
3 2
3 2
3 2
3 2
4 3
4 3

Sample Input:

10 10
####....##
##.......#
#....##...
#...####..
#...####..
#...####..
#.........
#...####..
....####..
*...####..
16
UURUURRULUULLUUD

Sample Output:

9 1
Crash! 9 1
9 1
8 2
6 4
Crash! 6 4
6 4
7 5
7 6
7 8
Crash! 7 10
7 10
7 10
6 10
4 10
3 10

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021年中国大学生程序设计竞赛女生专场

Code GYM103389I

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 11/01/2021 22:24:36

Related

Nothing Yet