- The Umbrella Problem: 2054 C语言
"Forget it," Garret complained, throwing down the controller to his PlayStation VIII, "this level is impossible." He had just "died" for the 17th time on level 54 of the game "Lemmings 9: Lost in Space".
"No it isn't," his brother Ferret replied, "and I can prove it." Ferret pulled his PlaySkool PDA from the back pocket of his Levi's Huggies.
"First, picture the level as a rectangular grid." Ferret punched a few of the buttons on his PDA and a rectangle appeared as he described. "Your character, a Lemming holding an umbrella, starts at the top of this rectangle. His goal is to reach the bottom without dying."
"I know that, you weasel, but what about the laser guns?" Garret whined.
"The name is Ferret, and I was just getting to that. If we represent the level as a rectangular grid, then the Lemming can occupy one square and each laser gun can occupy a square. Remember the laser guns are cyclic: they all shoot up the first turn, right the second turn, down the third turn, left the fourth turn, and then repeat the sequence."
"But you're forgetting the pits of lava!" Garret exclaimed.
"You didn't let me finish. Each pit of lava also occupies a square. And each plot of grass, the Lemming's destination, can also occupy a square. Then, it's just a matter of manipulating the Lemming and laser beams in a series of turns to determine if it is possible for the Lemming to reach the bottom without 'dying'."
"You think you're so smart, Ferret, let's see if you can explain that again in a clear, concise way."
The level will consist of a grid of squares. The way each laser beam and the Lemming moves can be described in "turns". To determine if the Lemming can reach the bottom of the level without dying, Ferret devised some rules:
Each turn will consist of two steps:
First, the laser guns will "fire" and maintain until the end of the turn, a beam in a direction dependent on the number of the turn. On the first turn, each laser gun will shoot up (all squares directly above a laser gun are "unsafe" and cannot be occupied by the Lemming); on the second turn, each laser gun will shoot right; on the third turn, each laser gun will shoot down; on the fourth turn, each laser gun will shoot left; on the fifth turn, the sequence will repeat.
R 0| L |<- The Lemming will always start in a column on row 0
o 1| | In this example, on the first turn, the laser beam
w 2| S | will occupy squares (3,0),(3,1); second turn, (4,2);
3| | third turn, (3,3),(3,4),(3,5),(3,6); fourth turn,
4| | (0,2),(1,2),(2,2); fifth turn (repeating), (3,0),(3,1), etc.
5| | (squares are represented using (column,row) notation)
6|GPPGG|<- The pits of lava and grass squares will always be
in the last row
Second, the Lemming will always move one row down, but to any one of three columns: one column to the left, one column to the right, or remain in the same column. In the above example, on the first turn the Lemming (L) could move to square (1,1), (2,1), or (3,1) (if he moved to (3,1), though, he would die because of the laser beam). However, on any turn the Lemming cannot move outside of the grid (i.e., he cannot move to column -1, or to a column number equal to the number of columns).
The level is considered "possible" if the Lemming can reach any "grass" square without dying after a series of turns.
The Lemming will die if at any point he occupies the same square as a laser gun, its beam, or a pit of lava. This includes:
The Lemming moving into a square a pit of lava occupies,
The Lemming moving into a square a laser gun occupies,
The Lemming moving into a square a laser beam occupies (even if it is a grass square!),
A laser gun firing a beam into a square the Lemming occupies
Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets. Each data set will describe the starting conditions of the level. A single data set has the following components:
Start line - A single line, "START x y", where 0 < x < 10 and x is the number of columns in the grid representing the level and 1 < y < 10 and y is the number of rows in the grid representing the level.
The next y lines will represent the rows of the level, starting with row 0 (the top). Each line will consist of x letters. The letters will represent components of the level as follows:
L - Lemming (there will only be one 'L' per data set, and it will always be in row 0)
S - laser gun (these squares will never be in the final row)
P - pit of lava (these squares will always be in the final row)
G - grass (these squares will also always be in the final row)
O - "empty" square of air
End line -- A single line, "END".
Following the final data set will be a single line, "ENDOFINPUT".
Output for each data set will be exactly one line. The line will either be "FERRET" or "GARRET" (both all caps with no whitespace leading or following).
"FERRET" will appear if the Lemming can make it safely (without dying) to any grass square at the bottom of the level after a series of turns.
"GARRET" will be output for a data set if it fails to meet the criteria for a "FERRET" line.
START 5 7
START 3 3
START 5 8
- 博客 在中国程序员是青春饭吗？
- 博客 程序员请照顾好自己，周末病魔差点一套带走我。
- 博客 和黑客斗争的 6 天！
- 博客 搜狗输入法也在挑战国人的智商！
- 博客 总结了 150 余个神奇网站，你不来瞅瞅吗？
- 博客 副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
- 博客 MySQL数据库面试题（2020最新版）
- 博客 如果你是老板，你会不会踢了这样的员工？
- 博客 我入职阿里后，才知道原来简历这么写
- 博客 优雅的替换if-else语句
- 博客 离职半年了，老东家又发 offer，回不回？
- 博客 2020阿里全球数学大赛：3万名高手、4道题、2天2夜未交卷
- 博客 男生更看重女生的身材脸蛋，还是思想？
- 博客 程序员为什么千万不要瞎努力？
- 博客 为什么程序员做外包会被瞧不起？
- 博客 当HR压你价，说你只值7K，你该怎么回答？
- 博客 面试：第十六章：Java中级开发（16k）
- 博客 面试阿里p7，被按在地上摩擦，鬼知道我经历了什么？
- 博客 面试了一个 31 岁程序员，让我有所触动，30岁以上的程序员该何去何从？
- 博客 大三实习生，字节跳动面经分享，已拿Offer
- 博客 程序员垃圾简历长什么样？
- 博客 《Oracle Java SE编程自学与面试指南》最佳学习路线图2020年最新版（进大厂必备）
- 博客 《Oracle Java SE编程自学与面试指南》最佳学习路线图（2020最新版）
- 博客 都前后端分离了，咱就别做页面跳转了！统统 JSON 交互
- 博客 字节跳动面试官竟然问了我JDBC？
- 博客 面试官：你连SSO都不懂，就别来面试了
- 博客 阿里面试官让我用Zk（Zookeeper）实现分布式锁
- 博客 终于，月薪过5万了！
- 博客 自从喜欢上了B站这12个UP主，我越来越觉得自己是个废柴了！
- 博客 代码注释如此沙雕，会玩还是你们程序员！