I think the following simple algorithm would work
A matrix is fantastic if and only if each row is either the same as the first row or the negative of the first row.
If we change "+" and "-" to $1$ and $-1$ then a matrix is fantastic if and only if it has rank $1$.
Consider the viewpoint where we have each "+" represented by $1$ and each "-" represented by $-1$. Each operation is now equivalent to multiplying a single row or a single column by $-1$. Each fantastic matrix can be obtained by applying a sequence of such operations to the matrix consisting entirely of $1$s.
Now, such an operation does not alter the rank of a matrix (if the changed row/column was a linear combination of the others then it still is) so any fantastic matrix necessarily has rank $1$. This proves the only if statement.
To prove the "if" statement, consider any matrix of rank $1$ with entries $\pm 1$. Identify all entries which are $-1$ in the top row, say they have indices $i_1, i_2, \ldots, i_m$.
Change all the entries in columns $i_1, i_2, \ldots, i_m$.
Then, the rows in the resulting matrix will either have all $1$s or all $-1$s. Select the rows which are all $-1$s and change these to get back to a matrix of all $1$s.