We may combine the operations on the same row or column, thus the final result of a series of operations can be realized as subtracting integer $x_i$ from each number of $i$-th row and subtracting integer $y_j$ from each number of $j$-th column. Thus, the matrix $A$ is good if and only if there exist integers $x_i, y_j$, such that $a_{ij} = x_i + y_j$ for all $1 \le i, j \le p$.

Since the entries of $A$ are distinct, $x_1, x_2, \dots, x_p$ are pairwise distinct, and so are $y_1, y_2, \dots, y_p$. We may consider only the case that $x_1 < x_2 < \cdots < x_p$ since swapping the value of $x_i$ and $x_j$ results in swapping the $i$-th row and $j$-th row, which is again a good matrix. Similarly, we may consider only the case that $y_1 < y_2 < \cdots < y_p$, thus the matrix is increasing from left to right, also from top to bottom.

From the assumptions above, we have $a_{11} = 1$, $a_{12}$ or $a_{21}$ equals $2$. We may consider only the case that $a_{12} = 2$ since the transpose of the matrix is again good. Now we argue by contradiction that the first row is $1, 2, \dots, p$. Assume on the contrary that $1, 2, \dots, k$ is on the first row, but $k+1$ is not, $2 \le k < p$, therefore $a_{21} = k+1$. We call $k$ consecutive integers a “block”, and we shall prove that the first row consists of several blocks, that is, the first $k$ numbers is a block, the next $k$ numbers is again a block, and so on.

If it is not so, assume the first $n$ groups of $k$ numbers are “blocks”, but the next $k$ numbers is not a “block” (or there are no $k$ numbers remaining). It follows that for $j = 1, 2, \dots, n$,

$y_{(j-1)k+1}, y_{(j-1)k+2}, \dots, y_{jk}$ is a "block", the first $nk$ columns of the matrix can be divided into $pn \times k$ submatrices $a_{i, (j-1)k+1}, a_{i, (j-1)k+2}, \dots, a_{i, jk}$, $i = 1, 2, \dots, p$, $j = 1, 2, \dots, n$, each submatrix is a "block". Now assume $a_{1, nk+1} = a$, let $b$ be the smallest positive integer such that $a+b$ is not on the first row, then $b \le k-1$. Since $a_{2, nk+1} - a_{1, nk+1} = x_2 - x_1 = a_{21} - a_{11} = k$, we have $a_{2, nk+1} = a+k$, therefore $a+b$ lies in the first $nk$ columns. Therefore, $a+b$ is contained in one of the $1 \times k$ submatrices mentioned above, which is a "block", however $a, a+k$ are not in this "block", which is a contradiction.

We showed that the first row is formed by blocks, in particular $k \mid p$, however, $1 < k < p$, and $p$ is a prime, which is impossible. So we conclude that the first row is $1, 2, \dots, p$, the $k$-th row must be $(k-1)p+1, (k-1)p+2, \dots, kp$. Thus up to interchanging rows, columns and transpose, the good matrix is unique, the answer is therefore $2(p!)^2$.