Let $p$ be a prime. We arrange the numbers in $\{1, 2, \ldots, p^2\}$ as a $p \times p$ matrix $A = (a_{ij})$. We can select any row or column and add 1 to every number in it, or subtract 1 from every number in it. We call the arrangement "good" if we can change every number of the matrix to 0 in a finite number of such moves. We aim to determine the number of good arrangements.

Assume we start with a good matrix and let $a_i$ and $b_j$ be the numbers of operations ("numbers add one" minus "numbers subtract one") on the $i$-th row and $j$-th column, respectively, to get a zero matrix. Then we should have:
$$a_{ij} + a_i + b_j = 0.$$
Summing up all these equations, we obtain:
$$\sum_{i=1}^p a_i + \sum_{j=1}^p b_j = -p \left( \frac{p^2 + 1}{2} \right).$$
As a result, it implies the sum of numbers that lie on $A_{1\sigma(1)}, A_{2\sigma(2)}, \ldots, A_{p\sigma(p)}$ is constant for all $\sigma \in S_p$.

By comparing these equations, we find that the first row of the matrix is just a translation of the second row, i.e., $A_{1i} - A_{2i}$ is constant for $1 \leq i \leq p$. This is true for any two other rows as well.

Thus, the problem boils down to finding $a_1, a_2, \ldots, a_p \in \{1, 2, \ldots, p^2\}$ and $0 = x_1, x_2, \ldots, x_{p-1} \in \mathbb{Z}$ such that:
$$B_i = \{a_1 + x_i, a_2 + x_i, \ldots, a_p + x_i\}$$
represents the $i$-th row of matrix $M$ for $1 \leq i \leq p$, representing a partition of $\{1, 2, \ldots, p^2\}$.

Without loss of generality, we can assume $1 = a_1 < a_2 < \ldots < a_p$ and $0 = x_1 < x_2 < \ldots < x_{p-1}$. We try to prove that either $x_i = i-1$ (first column is $\{1, 2, \ldots, p\}$) or $a_i = i$ (first row is $\{1, 2, \ldots, p\}$).

If $a_2 > 2$ and $x_2 > 1$, then neither the first row nor any other rows contain 2. We have two cases to consider:

1. $x_2 = 1$:
This is straightforward. If $x_3 > 2$, then there is no possible position for 3, so $x_3 = 2$. Continuing in the same way, we find $x_i = i-1$.

2. $a_2 = 2$:
Let $k$ be the greatest number such that $a_i = i$ for all $1 \leq i \leq k$. Then where is $k+1$? Yes, $x_2 = k$ and $k+1, \ldots, 2k$ lie below $1, 2, \ldots, k$. Playing around with possible positions, we arrive at the matrix:
$$M = \begin{bmatrix} 1 & 2 & \ldots & k & 2k+1 & 2k+2 & \ldots & 3k & 4k+1 & \ldots \\ k+1 & k+2 & \ldots & 2k & 3k+1 & 3k+2 & \ldots & 4k & 5k+1 & \ldots \\ & & & & & \\ & & & & & \end{bmatrix}$$
This matrix implies $k \mid p$, which is a contradiction since $p$ is prime.

Therefore, in both cases, we can suppose that $a_i = i$. This argument works symmetrically for columns as well. Hence, the number of good arrangements is:
$$2(p!)^2.$$
The answer is: $\boxed{2(p!)^2}.$