Disco Zoo Complexity A popular mobile game, DiscoZoo, is about "rescuing" animals from a 5x5 grid of cells. Each animal represents a unique pattern (some have 3 cells, some have 4). The object is that, given this 5x5 grid, find all (or as many as possible) of the given animals within 10 turns, where the pattern of animals can be at any place within the grid (but cannot be rotated, change size, etc. - only translated such that all the coordinates of each animal are valid, and there is only one animal per square). We can only "get" an animal if we can successfully find each of the squares of that animal within the number of turns left; otherwise, we do not.

Here is an example. The sheep has a pattern of 4 horizontal adjacent squares, so clearly the squares (5, 2) (indexing from 1 and as (row, col)) and (5, 5) will be a sheep (and thus get the sheep). For the rabbit, it has a pattern of 4 vertical adjacent squares, so the squares (2, 1) and (4, 1) will be the rabbit. For the cow, it has a pattern of 3 horizontal adjacent squares, and since square (4, 2) was selected (and no animal placed there), the only square left for the cow is (4, 5). This is assuming that we do have attempts left (but there aren't any for this example).



More formally, we are given a 2D array $a[1..n][1..n]$, and $m$ animals $A_1,...A_m$ such that $A_i$ has value $p_i$. In the grid are the values of the $p_i$'s (in their respective positions) and all the rest are 0. Each cell either has 0 or one non-zero value (i.e., only one animal). However, none of the values are given to us at the start. Once we "select" a cell, that cell's value is revealed to us. Our objective is to find all or the maximum possible number of non-zero cells in the grid within $g$ turns.

What is the complexity of this problem in general?

Edit: after some thinking about the problem, let's restrict ourselves to having $m$ copies of the same animal $A$, and let that animal be a 2x2 square (i.e., occupies coordinates $(x, y), (x+1, y), (x, y+1), (x+1, y+1)$). What is the complexity of this version of the problem? 

Even if we restrict further by looking at 1x1 squares, this is equivalent to finding nonzero elements in the matrix - it is trivially solvable in $\Theta(n^2)$ time, but can we do better?
For the 2 by 2 block version in the edit, consider the promise problem where there is guaranteed to be just one block in each 3 by 3 region, where the regions have coordinates $(3i+1,3j+1)$ to $(3i+3,3j+3)$ for non-negative integers $i$ and $j$.  By an adversary argument, in the worst case one may have to probe one square in each of the first $\lfloor n/3\rfloor^2-m$ regions and then two squares in each of the last $m$ regions, so in the worst case at least $\lfloor n/3\rfloor^2+m \ge ((n-2)/3)^2+m\ge \Omega(n^2)$ probes.