Type a word on a grid keyboard with a jump limit

You are typing a word with one finger on an unusual keyboard: an m x n grid of characters. Moving the finger from cell (r1, c1) to cell (r2, c2) covers a Manhattan distance of |r1 - r2| + |c1 - c2|. The finger can never move more than k in a single jump.

Implement:

def can_type(keyboard: list[str], k: int, word: str) -> bool

Return True if word can be typed: the finger starts on any key holding word[0], and every move to the key for the next letter is at most k away. Staying on the same key (distance 0) is allowed.

Notes and constraints

• keyboard has m rows of equal length n; 1 <= m, n <= 50.
• A character may appear on more than one key. You may use any copy.
• 0 <= k, and word has up to 1000 characters.
• If a letter of word is not on the keyboard, the answer is False. An empty word is True.

Example 1

keyboard = ["qwertyuiop",
            "asdfghjkl;",
            "zxcvbnm,./"]
can_type(keyboard, 2, "were")  -> True   # every jump is 1
can_type(keyboard, 8, "quiz")  -> False  # i (0,7) to z (2,0) is 9
can_type(keyboard, 9, "quiz")  -> True

Example 2 (repeated keys)

keyboard = ["ba...a",
            ".....c"]
can_type(keyboard, 1, "bac") -> False

The a beside b is 5 away from c, and the a above c is 5 away from b. No choice of a works.

Aim for better than trying every combination of key copies.