Call the four boundary walls going from the top clockwise A, B, C, D. Call a set of cells a connected component if you can start from any of them and walk to any other by alternating color cells. We will show that there exist a connected component which touches either A and C or B and D (that will be sufficient). Let x be the top left corner cell, and consider the maximum connected component that contains it. If that connected component touches either B or C, then we are done. Otherwise we have a following Lemma: A walk alongside a maximum connected components perimeter is a good walk. Proving this is not hard if we use the given condition that any 2x2 square contains at least 2 different colors. Now, using this Lemma, we see that the perimeter of a maximized connected component is a connected component itself which touches A and D. So we maximize this connected component and repeat the procedure.