The Umbrella Problem: 2054 - 问题

"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."

"Certainly":

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:
1. 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.
```
Example:

    Column

    01234

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
```
2. 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:
1. The Lemming moving into a square a pit of lava occupies,
2. The Lemming moving into a square a laser gun occupies,
3. The Lemming moving into a square a laser beam occupies (even if it is a grass square!),
4. A laser gun firing a beam into a square the Lemming occupies

1984: The Umbrella Problem: 2054

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

来源/分类