最近,有一些繁殖力很强的老鼠在下水道非常猖獗,灭鼠特工队正在计划消灭这些老鼠。下水道只有东西方向和南北方向的管道,如图所示。
灭鼠特工队的队员拥有强大的武器。他们将在某些时刻t在某些位置(x,y)放置武器。他们所使用的武器包括:
1. 强力炸弹:它的攻击范围限定在管道内部,是沿竖直和水平方向,离(x,y)的距离不超过L的区域,但是不能穿透下水道壁。它将在放置之后立刻爆炸,且攻击范围内的老鼠将被全部炸死。
2. 神秘射线:它的攻击范围是以(x,y)为圆心,半径为R的圆,而且可以穿透下水道壁。射线在时刻t施放后,将使攻击范围内的所有老鼠立刻陷入昏迷状态,失去知觉,停止一切生理活动,待到第t+3时刻才能恢复(保持失去知觉前的朝向)。如果在昏迷状态中再次受到射线攻击,那么它将再推迟3个时刻恢复。例如,若老鼠在时刻t和时刻t+1个受到一次射线的攻击,则它要昏迷到第t+3+3时刻才能恢复知觉。恢复知觉以后,老鼠将继续以前的生理活动。
3. 定时炸弹:它的攻击范围仅包括(x,y)。它在时刻t放置后,将在第t+3时刻爆炸,爆炸时处在(x,y)点的老鼠将全部被炸死。
4. 生物炸弹:它的攻击范围仅包括(x,y)。它将在放置之后立刻爆炸,使处在(x,y)点的所有老鼠的性别改变(无论大小,雌变成雄,雄变成雌),但不影响老鼠的正常生理活动。
虽然特工队的实力很强,但是老鼠的实力也不容忽视。
我们定义,相邻两个时刻之间是一个时间单位。从t=0时刻开始,每只老鼠就从初始位置向某一初始方向运动。只要前方有管道,如上图中沿方向N到达点A,老鼠就会一直向前走,运动速度为1。否则,如果只有左边或者只有右边有管道,如上图中沿方向E到达点B时,再不能沿原方向继续前进,它就会花费一个时间单位朝该方向原地转动90度,即它将改变方向朝向S。如果它左边和右边都有管道,如上图中沿方向W到达点C,老鼠会回忆这是第几次处于这种情况。如果是第奇数次遇到,它会向左转,第偶数次就向右转。如果它处于一条死路的尽头,如上图中沿方向W到达点D,那么它会花费两个时间单位连续向右转两次,即它将改变方向朝向E。
如果在t时刻某点恰好只有两只老鼠,一只为成年雄老鼠,一只为成年雌老鼠,则它们将会因为进行繁殖而在该点停留两个单位时间,t+2时刻会在该点对每个有管道的方向生出一只朝着该方向的小老鼠,南北方向为雄小老鼠,东西方向为雌小老鼠。如上图中的C点,t时刻恰好只有两只老鼠,它们都已成年且性别相异,那么在第t+2时刻就会在该点生出三只小老鼠,它们分别朝向N、S、E,性别分别是雄性、雄性、雌性。小老鼠一出生就立刻开始移动,而成年老鼠需要再休息一个时间单位,即在t+3时刻继续活动(两只老鼠都保持生育前的朝向)。小老鼠需要成长5个时间单位才会长成为成年老鼠。
特工队现在制定了一套灭鼠计划,其中包括在下水管道放置武器的位置、时间和类型。你需要帮他们计算灭鼠行动的效果,如果在该计划实施的过程中,老鼠的数量超过了某个限定值,就会爆发鼠疫。