Disco Zoo Complexity
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.