Detailed rules

- Given a grid of the size
`width`×`height`, with0 0 being the upper left corner in`column``row`notation. - The grid contains only open (passable) tiles and wall tiles (impassable).
- There are eight possible directions of movement:
`N``NE``E``SE``S``SW``W``NW`, where`N`means "up", and`E`"right". - Moving diagonally is possible only when tiles of both related cardinal directions are passable.

For example, going`NE`requires both`N`and`E`neighboring tiles to be open. - The result of the preprocessing phase is encoded as a set of passable tiles, each formatted as
`column row N NE E SE S SW W NW`, where`column row`contain the tile coordinates, and the remaining numbers are distances in the corresponding directions.

For example,2 0 3 -2 1 4 2 -1 -1 4 means that for the tile of column 2 and row 0 going north there is a jump point 3 tiles away, going northeast there is a wall 2 tiles away, etc. - The JPS+ runtime procedure should work as described in the section 14.7 of the cited publication.
- You need to implement the open list with a priority queue.
- The heuristic function in use for the A* part shall be the octile distance:

For two points(x1,y1) and(x2,y2) , the octile distance is given bydx + dy + (√2 - 2) . min(dx,dy) wheredx = |x2-x1| anddy = |y2-y1| . - For each node popped from the open list, your goal is to send one line, containing information about this node.
- Each line should be formatted as
`nodeColumn nodeRow parentColumn parentRow givenCost`, where`nodeColumn nodeRow`contains the coordinates of the current node,`parentColumn parentRow`contain the coordinates of the node's parent, and`givenCost`is the cost of traversing from the start to the node. - When the algorithm finds that path does not exist (open list is empty), you should send
NO PATH .