function exist(board, word) {
    function bfs(row, col, idx) {
        if (board[row][col] !== word[idx]) return false;

        if (idx === word.length - 1) return true;

        board[row][col] = '0';

        for (const [rowDelta, colDelta] of dirs) {
            const newRow = row + rowDelta;
            const newCol = col + colDelta;
            if (isValidCoord(newRow, newCol) && bfs(newRow, newCol, idx + 1)) {
                return true;
            }
        }

        board[row][col] = word[idx];
        return false;
    }

    function isValidCoord(row, col) {
        return row >= 0 && row < numRows && col >= 0 && col < numCols;
    }

    const numRows = board.length;
    const numCols = board[0].length;
    const dirs = [
        [1, 0],
        [-1, 0],
        [0, 1],
        [0, -1],
    ];

    for (let row = 0; row < numRows; row++) {
        for (let col = 0; col < numCols; col++) {
            if (bfs(row, col, 0)) return true;
        }
    }

    return false;
}
