Word search in a straight line

Given an m x n grid of uppercase letters board and a string word, decide whether word appears in the grid along a straight line.

A match starts at some cell and reads len(word) consecutive cells in one of the 8 directions: left, right, up, down, or one of the four diagonals. The direction may not change partway through the word, and the line may not wrap around the edge of the grid. (Because the direction is fixed, no cell is used twice.)

Implement:

• exists(board, word) -> bool: whether the word appears anywhere.
• find_all(board, word) -> list[(row, col, (dr, dc))]: every starting cell and direction where the word appears, in row-major order. Report a one-letter word once per matching cell.

Constraints

• 1 <= m, n <= 200
• 0 <= len(word) <= 200
• An empty word counts as found.

Example

P L A N
E O R K
N I D S
S M T Y

• exists(board, "PEN") returns true: column 0, going down.
• exists(board, "NAL") returns true: row 0, going left.
• exists(board, "POD") returns true: the diagonal from the top-left corner.
• exists(board, "POLE") returns false. The letters are adjacent, but the path turns.
• find_all(board, "POD") returns [(0, 0, (1, 1))].

Expect follow-ups: allow the path to turn (without reusing a cell), search for many words at once, or answer many queries against one large grid.

Reconstructed from the reported question; details may differ from what interviewers ask.