Recover a matrix with minimum number of queries
Let me consider the case $n = m$ for concreteness. Since the entropy of $A$ is $n\log n$ and each question results in at most one bit of information, at least $n\log n$ queries are needed.

Suppose that a question is selected uniformly at random. The probability that the answer is zero is $(1-1/n)^n \approx 1/e$, and in that case, we can mark all the queried entries as zero. Imagine making such queries until $N$ are successful. This is the same as making $N$ queries, each of which involves $n$ zero positions at random. The probability that a particular zero position is never queried is 
$$
\left(1 - \frac{n}{n(n-1)}\right)^N \approx e^{-N/n}.
$$
Therefore after $(2+\epsilon) n\log n$ queries, the probability that a particular zero position is never queried is at most roughly $n^{-2-\epsilon}$, and so the probability that not all zero positions are revealed is at most $n^{-\epsilon}$. We conclude that $(2e+\epsilon) n\log n$ queries suffice to reveal the matrix with probability $1-o(1)$.

We can repeat the calculation for general $m$, but the bounds no longer match. For example, when $m$ is very large, the answer to most questions will be zero, and so bounding the amount of information obtained from a single query by one bit is too generous.