Write a function greedy_path(matrix) that takes in the same grid as Q1, and returns:

The locally optimal path using a "Best First Search" strategy as a list of tuples (coordinates).

The total score as an integer.

Your function should return the above the result as a tuple in form (path, score).

The parameters to this function are as follows:

matrix is a list of lists, where the "outer lists" denote rows and "inner lists" denote columns. Each cell is given an integer value denoting the "score" in the cell.

Note, that you are encouraged to make any additional helper function(s) to make your code become readable and neat (as there are marks awarded to this criteria).

We also strongly suggest you draw out the grid and "mimic" a Best First Search before you write the code prior to implementing.

Here's an example call to your function:

greedy_path([[0,0,-150,0],[0,1000,0,0],[-1000,0,-1000,0],[0,0,150,0]])

>>> ([(0, 0), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)], 1000)

greedy_path([[0, -1000, 150, 150, 150], [1000, 0, 0, -150, 150], [0, -1000, 0, 0, 150], [0, -1000, -1000, -1000, 150], [1000, 1000, 1000, 1000, 0]])

>>> ([(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)], 1300)

greedy_path([[0, 1000, -1000, 0, 150, 150, 150],

[1000, 1000, -1000, 0, -150, -150, -150],

[1000, -1000, -1000, 0, 0, 0, 0],

[1000, -1000, 0, 0, 0, 0, 0],

[1000, -1000, 0, 0, 0, 0, 0],

[1000, -1000, 0, 0, 0, 0, 0],

[1000, 1000, 1000, 1000, 1000, 1000, -150]])

>>> ([(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), (5, 2), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)], 850)