Save Spacemen spiff

general
1

hey i guys i have a problem and i am not getting how to solve it…
help me some suggestions…

Problem 2: Save Spaceman Spiff

Spaceman Spiff has crash landed on Planet Quorg. He has to reach his ship quickly. But the evil Yukbarfs have stolen many Death Ray Blasters and have placed them along the way. You’ll have to help him out!

Spaceman Spiff is initially at the top left corner (1,1) of a rectangular N × M grid . He needs to reach the bottom right corner (N,M). He can only move down or right. He moves at the speed of 1 cell per second. He has to move every second-that is, he cannot stop and wait at any cell.

There are K special cells that contain the Death Ray Blasters planted by the Yukbarfs. Each Blaster has a starting time t and a frequency f. It first fires at time t seconds, followed by another round at time t+f seconds, then at time t+2f seconds …. When a Blaster fires, it simultaneously emits four pulses, one in each of the four directions: up, down, left and right. The pulses travel at 1 cell per second.

Suppose a blaster is located at (x,y) with starting time t and frequency f. At time t seconds, it shoots its first set of pulses. The pulse travelling upwards will be at the cell (x,y-s) at time t+s seconds. At this time, the pulse travelling left will be at cell (x-s,y), the pulse travelling right will be at cell (x+s,y) and the pulse travelling down will be at cell (x,y+s). It will fire next at time t+f seconds. If a pulse crosses an edge of the grid, it disappears. Pulses do not affect each other if they meet. They continue along their original path. At any time, if Spaceman Spiff and a pulse are in the same cell, he dies. That is the only way pulses interact with Spaceman Spiff. Given these, you should find the least time (in seconds) in which Spaceman Spiff can reach his ship safely.

As an example consider a 4×4 grid that has only one Blaster, at (3,2), with starting time 1 and frequency 3. In the grids below, S denotes Spaceman Spiff, B denotes the blaster and P denotes a pulse. The sequence of grids describes a successful attempt to reach his ship that takes 6 seconds.

   t=0                t=1                t=2                t=3  
S  .  .  .         .  S  .  .         .  .  S  .         .  P  .  S
.  .  .  .         .  .  .  .         .  P  .  .         .  .  .  .
.  B  .  .         .  P  .  .         P  B  P  .         .  B  .  P
.  .  .  .         .  .  .  .         .  P  .  .         .  .  .  .



   t=4                t=5                t=6
.  .  .  .         .  .  .  .         .  P  .  .
.  .  .  S         .  P  .  .         .  .  .  .
.  P  .  .         P  B  P  S         .  B  .  P
.  .  .  .         .  P  .  .         .  .  .  S

Input format

Line 1: Three space separated integers N, M and K, describing the number of rows and columns in the grid and the number of Blasters, respectively.

Lines 2 to K+1: These lines describe the K blasters. Each line has four space separated integers. The first two integers on the line denote the row and column where the Blaster is located, the third integer is its starting time, and the fourth integer is its frequency.

Output format

The first line of output must either consist of the word YES, if Spaceman Spiff can reach his ship safely, or the word NO, if he cannot do so. If the output on the first line is YES then the second line should contain a single integer giving the least time, in seconds, that it takes him to reach his ship safely.

Sample Input 1

4 4 1
3 2 1 3



Sample Output 1

YES
6



Sample Input 2

5 5 2
5 1 1 2
4 4 1 2



Sample Output 2

YES
8
2

The critical insight here is that Spiff can visit a given cell only at a single specific point in time.

Hence, you can iterate over each of the blasters, checking each of the cells in its row and column, marking them as unsafe if there is a pulse passing through them at the time Spiff will get there.
After that, just run over the cells from the bottom most cell to the top most cell, calculating the number of paths that exist from each cell to the bottom-right corner. Iff this number is non-zero for the upper-left column, then Spiff is through, else he’s dead.
Also, the length of the path follows from the first insight. It’s the same regardless of which cells you visit. Where the grid size is N * M, the length is (N - 1) + (M - 1).
I’ll write some code for this, and attach it here as soon as possible.
Cheers.

1 Like
3

Regarding pongli 's answer:

Should I consider pulses to be unwalkable while calculating the minimum cost path?

4

Yes. I have not done this problem yet, so I can’t attach code

5

where can we find the solutions of previously posted questions ??