Shortest path through a digit grid with diagonal moves

You are given an m x n grid of digits. A cell holding 0 is a wall; a cell holding 1 through 9 is open. Starting at the top-left cell (0, 0), find a shortest route to the bottom-right cell (m - 1, n - 1).

From any cell you may step to any of its eight neighbours (up, down, left, right, and the four diagonals), as long as the neighbour is inside the grid and open. Every step costs the same.

Implement:

• shortest_path(grid) -> List[Tuple[int, int]]: the cells of one shortest path, in order, starting with (0, 0) and ending with (m - 1, n - 1). Return [] if no path exists (including when the start or end cell is a wall).
• shortest_path_length(grid) -> int: the number of cells on that path, or -1 if none exists.

If several shortest paths exist, any one of them is accepted.

Constraints

• 1 <= m, n <= 100
• grid[i][j] is an integer from 0 to 9.

Example 1

grid = [[1, 2, 0],
        [0, 5, 0],
        [7, 0, 9]]

shortest_path(grid)        -> [(0, 0), (1, 1), (2, 2)]
shortest_path_length(grid) -> 3

Example 2

grid = [[1, 1, 0, 0],
        [0, 0, 0, 1]]

shortest_path(grid)        -> []
shortest_path_length(grid) -> -1

Interviewers often follow up by treating each digit as the cost of entering its cell, by asking for every shortest path, or by forbidding diagonal moves that cut a wall's corner.