You are to write a function road_to_freedom(current_pos, goal_pos, matrix), where:

• current_pos is Eve's current coordinate in form (x, y);
• goal_pos is the goal coordinate in form (x, y);
• and matrix is the nested list representation you should be familiar with from Project 1.

The function should return the next coordinate with the highest heuristic score.

• If a tie occurs, then precedence is given first to the coordinate closer to the goal location.
• If there is also a tie in the manhattan distance, then you should return the coordinate using the order of preference from North going clockwise (N, NE, E, SE, S, SW, W, NW).

This tie breaking system is only for this question.

The heuristic is: Score - (100 x Manhattan Distance). Refer to the previous slide for more details.

For this question, you may assume the following:

• You can assume that the input arguments are syntactically correct given the definitions, and will always be non-empty.
• current_pos and goal_pos will always both exist within the matrix, and will never be on the same coordinate.
• You can assume the grid passed through as matrix will always have dimensions 22 or greater.

Refer to the previous slide for the heuristic definition.

Remember that this is an assessment task, and the work must be your own. It is illegal for others to do this work on your behalf.

Here are example calls to your function:

>>> road_to_freedom((0,0),(2,2), [[0,1000,-500],[1500,1000,1000],[-500,0,1000]])

(0, 1)

>>> road_to_freedom((0,1),(2,0), [[1000,0,1500],[1000,1000,0],[-500,0,0]])

(0, 0)

>>> road_to_freedom((1,1),(1,2), [[1000,1000,1500],[1000,0,0],[1500,1000,1000]])

(0, 2)

In python please