A solution with complexity $\mathcal{O}(T{N}^2)$:

For each second, starting with $0$, we compute a matrix of $1$s and $0$s, where a $1$ denotes a square reachable by the knight in the respective second. The matrix for second $0$ has $0$s in all positions, except for the starting position of the knight. From each matrix, we can compute the matrix for the next second, up to second $T$. The next matrix is computed by mapping all $1$s to all squares reachable by any of the $8$ possible jumps from that square, and then zeroing out all positions blocked during the next second.

The memory complexity of this algorithm is $\mathcal{O}(N^2)$, since we need only two matrices (the current and the next one) at any moment. This solution is worth $40\mathrm{\%}$ of points.

A solution with complexity $\mathcal{O}(TN)$:

Instead of the matrix of $1$s and $0$s, we will use a sequence of numbers, where each number represents a row of the matrix and its binary digits correspond to the $1$s and $0$s from the previous solution. For simplicity, we will continue to use the term matrix in the remainder of the description.

The mapping of $1$s in all $8$ directions can now be implemented using bit operations, which is more efficient than the previous solution.

The remaining problem is quickly computing the matrix of squares blocked in second $t$. Notice that if $t$ is divisible by $K_{ij}$, then the square $(i,j)$ is blocked during second $t$.

If $K_{ij}$ is greater than $1000$, we can simply generate all moments when the square will be blocked, since there will be less than $1000$ such moments.

If $K_{ij}$ is less than $1000$, the problem can be solved using prime factorization. Notice that, if $K_{ij}$ divides $t$, all prime factors of $t$ (including the ones with exponent $0$) must have greater or equal exponents than the corresponding exponents in the factorization of $K_{ij}$.

Let us denote by $F(p^q)$ the matrix with a $1$ in position $(i,j)$ if $q$ is greater than or equal to the exponent of the prime number $p$ in the factorization of $K_{ij}$.

Now the matrix of squares blocked in second $t$ can be expressed as:

$$\begin{array}{}\text{(1)}& {\displaystyle F(p_1^{q_1})\mathrm{\&}F(p_2^{q_2})\mathrm{\&}\dots \mathrm{\&}F(p_k^{q_k})}\end{array}$$

where $p_1,p_2,\dots ,p_k$ are all primes less than $1000$, $q_1,q_2,\dots ,q_k$ are their exponents in the factorization of $t$, and $\mathrm{\&}$ is the bitwise AND operation.

The direct computation of the above expression $(1)$ is slow. However, notice that at most $7$ primes in a factorization will have positive exponents, while all other exponents will be $0$.

Before the main algorithm, we will precompute, for each interval $[x,y]$, the following:

$${\displaystyle G(x,y)=F(p_x^0)\mathrm{\&}F(p_{x+1}^0)\mathrm{\&}\dots \mathrm{\&}F(p_y^0)}$$

The expression $(1)$ can now be quickly computed by using $F(p^q)$ for all primes with a positive exponent, and the precomputed $G$ for all other primes (with exponents of $0$, grouped in at most $8$ intervals), combining all values with a bitwise AND.

Now that we can compute the matrix of squares blocked in second $t$, we can simply apply it to the current matrix of possible positions using a bitwise AND, thus obtaining the final matrix for second $t$.