Micro-Drill #188 — Word search on grid

def exist(board, word):
    m, n = len(board), len(board[0])
    def dfs(i, j, k):
        if k == len(word): return True
        if i < 0 or i >= m or j < 0 or j >= n: return False
        if board[i][j] != word[k]: return False
        tmp, board[i][j] = board[i][j], '#'  # mark visited
        for di, dj in (0,1),(0,-1),(1,0),(-1,0):
            if dfs(i+di, j+dj, k+1): return True
        board[i][j] = tmp  # unmark
        return False
    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0): return True
    return False