Not sure if this is what you were going for, but it's what I thought of when I read your hint.
In order for a square at coordinates xn,ym to be painted, two of four other squares have to also be painted:xn-1,ym; xn+1,ym; xn,ym-1; or xn,ym+1. Now, if N is the largest x coordinate you paint initially and M is the largest y coordinate you paint initially, it will be impossible to paint another square with x=N+1 or y=M+1, because the farthest you can reach is N,M. Why? In order to paint an exterior square (N+1,y or x,M+1), three of the four potentially required squares are not available, and so we're upwardly bounded at N,M. Similarly, if your smallest x and y coordinates are P and Q, respectively, you can't automatically paint a square with x and y coordinates less than P and Q. So our array of potentially painted squares is bounded in the x-y plane by the x-y coordinates of the initially painted squares.
The other thing you find is that the four squares listed above are connected to each other diagonally. I'm probably dancing all around the proof, but it should be possible to show that the most efficient way to paint an entire array from P,Q to N,M is to start with squares which extend the full range of P,Q to N,M and are all connected to each other diagonally. So you could start at P,Q and proceed diagonally up and to the right until you reach x=N or y=M, then turn 90 degrees and keep doing the same until you've hit the boundary on the other axis. In fact, if there is a gap in the diagonal, two smaller arrays are created, each with their own P,Q and N,M, and unless P2,Q2 is less than N1,M1, the two arrays will be independent and you'll never be able to paint the whole array from P1,Q1 to N2,M2.
