Jelly Jump (Large)
InterviewTime limit2sMemory limit128 MB
Given an N by N board where each cell holds a jump length, decide whether Jelly can travel from the top-left cell to the bottom-right cell moving only right or down.
- Level
Easy3 of 10
- Topics
- Dynamic programming, Matrix, DFS, Brute force
- Solved
- No attempts yet
Problem
'Jelly' is a jelly that loves to jump. Bored with plain jumping, 'Jelly' wants to try a new jumping game. The rules of the new jumping game are as follows.
- 'Jelly' can move only inside a square region whose width and height have the same number of cells. If 'Jelly' leaves the square region, it falls to the floor and immediately loses the game.
- 'Jelly' always starts at the topmost, leftmost cell of the square. It never starts anywhere else.
- 'Jelly' can move only right or down. It cannot move up or left.
- The moment 'Jelly' reaches the bottommost, rightmost cell, the game ends immediately with 'Jelly' as the winner.
- The number of cells 'Jelly' moves in one jump equals the number written on the cell it is currently standing on. It cannot move more or fewer cells than that number.
'Jelly' liked the new game and kept playing until it finally reached the final stage. However, the region has grown so wide that it can no longer tell whether the game can be won. 'Jelly' asked you, a capable programmer, to find out whether it can win in the given region. Help 'Jelly' determine whether it can reach the endpoint (the bottom-right cell) in the given game region!
Input
The first line of input gives the size N (2 ≤ N ≤ 64) of the game region.
From the second line to the last line of input, the cells (map) of the game board are given.
The winning point of the board (the bottom-right cell) has -1 written on it, and every other cell has an integer between 0 and 100 inclusive.
Output
If 'Jelly' can reach the endpoint, print "HaruHaru" (without quotation marks); if it cannot, print "Hing" (without quotation marks), on one line.