文档介绍：杂题大拼盘清华大学计42班金恺第一题新L游戏?问题描述–一个n行m列的棋盘,里面有一个或0个格子已经损坏。请在棋盘上放一些L棋子(如下),使每个未损坏的格子都恰巧被一个L拼块覆盖。?例如?输入有若干行(不超过100),每行为一组数据:–每行四个整数n,m,x,y;若x=0,y=0则表示所有格子都未损坏,否则表示第x行第y列的格子已损坏。?如果有解输出“I know!”否则输“No ans!”?数据范围 1≤n,m≤10100输入样例:5 5 1 15 6 0 09 3 0 010000 10000 5000 4000输出样例:I know!I know!No ans!I know!第二题消灭魔鬼?有N×M的格栅,每个格子不是平地就是障碍物(边界为障碍物)。?光线能水平或竖直的在平地上行进,但是遇到障碍物就会引发爆炸。?某些平地上已经事先安放上了镜子,有两种方向的镜子(都是双面的)?光线射在镜子上就会反射,满足反射角=入射角。镜子#1镜子#2?战士手拿激光枪站在A格的中心,魔鬼站在B格中心(A、B格都是平地且A≠B),请帮助战士消灭魔鬼:?在某些平地上添加一些镜子,然后告诉战士往哪个方向开激光枪。?数据范围:4≤N,M≤1000?约束:–任意两面镜子(包括事先放好的和你新添加的)都不能放在同一格上;–不能让任何一个障碍物爆炸;–数据保证有解;–镜子越少越好。AB平地障碍物AB?输出最小需要添加的镜子数?此例输出2进一步思考?扩展–用最小费用消灭魔鬼?删除原有镜子,费用f1,?改变镜子的方向,费用f2,?添加新的镜子,费用f3,?移除障碍物,费用f4。第三题机器人迷宫?有一个n×m的迷宫,每个格子不是平地就是障碍物(边界都是障碍物)。有p个机器人,全都站在平地上。?某一时刻,你可以向所有机器人发布相同的指令,指令有N、S、W、E,告诉机器人向某个方向前进。N表示向上,S表示向下,W表示向左,E表示向右。?如果某个机器人能够往该方向前进(即不碰到障碍物)则向该方向移动一格,否则原地不动。要求用不超过maxint条指令集结所有机器人——即让他们到达同一位置。?数据范围:n,m≤50 , p≤20 。?输出:–一个ESWN序列。序列长度不能超过maxint;要求所有机器人按着这个序列执行后到达同一格。思路?2个机器人若在某个时刻T在同一位置,那么T时刻以后永远处在同一位置;?先处理P=2,即两个机器人?然后每次选择两个位置不同的机器人,把他们合并,直到所有机器人都在同一个位置。?如何集结指定的2个机器人??追赶法……