Here's (what I think is) a simpler proof of Albert's lemma than the one in loopy_wall's answer. We'll find either a king-path of 0-squares connecting N and S sides, or a king-path of 1-squares connecting W and E sides. The basic idea is to walk along the boundary between 0-squares and 1-squares until we reach an edge of the board.

First of all, let's add imaginary 0-squares just outside the N and S sides of the board, and imaginary 1-squares just outside the W and E side of the board. (Obviously these make no difference to the existence of the paths we seek.) We don't add imaginary squares outside the corners.

At every new square-corner we reach, we have 0 behind us to our left and 1 behind us to our right. Pick the leftmost available direction that also has that property. (There always is one, unless we have hit a corner.)

If we reach the SW corner (or indeed the S side), then to our left we have constructed a N-S 0-path. If we reach the NE corner (or indeed the E side), then to our right we have constructed an E-W 1-path. We cannot return to the NW corner or reach the SE corner -- the edges there have 0 on the right or 1 on the left.

But it also can't be a later edge. Suppose our sequence of edges goes ..., e, f, ..., e', f, ...; e, e', f all have 0 on the left and 1 on the right, and f is the leftmost such edge after e and also after e'. That is, if you imagine pointing backwards along e and swinging your arm clockwise until it reaches f, it's always pointing into a 0-square when you do that; likewise with e',f. But if e,e' are not the same edge, one of those arm-swings must go past either e or e', which is impossible because each of those edges has 0 on one side and 1 on the other.

Here's (what I think is) a simpler proof of Albert's lemma than the one in loopy_wall's answer. We'll find either a king-path of 0-squares connecting N and S sides, or a king-path of 1-squares connecting W and E sides. The basic idea is to walk along the boundary between 0-squares and 1-squares until we reach an edge of the board. So here's an example board; red is for 0-squares, 1 for 1-squares. Alongside it, I've shown the path we will end up taking along the boundary, and then the king-path it enables us to construct.

So here's the actual construction. Stuff in italics is explanatory and accompanies the diagrams.

First of all, let's add imaginary 0-squares just outside the N and S sides of the board, and imaginary 1-squares just outside the W and E side of the board. (Obviously these make no difference to the existence of the paths we seek.) We don't add imaginary squares outside the corners.

At every new square-corner we reach, we have 0 behind us to our left and 1 behind us to our right. Pick the leftmost available direction that also has that property. (There always is one, unless we have hit a corner.)

Here's how we begin with the board above: we start at the NW corner; then we head S rather than E because that puts red (0) on our left and blue (1) on our right as required; at the next grid-point we turn left to keep red on the left and blue on the right.

At this point we could continue either northward or southward and have red on our left and blue on our right! We choose to go northward, because that lets us turn left as far as possible / right as little as possible while satisfying that condition.

If we reach the SW corner (or indeed the S side), then to our left we have constructed a N-S 0-path. If we reach the NE corner (or indeed the E side), then to our right we have constructed an E-W 1-path. We cannot return to the NW corner or reach the SE corner -- the edges there have 0 on the right or 1 on the left.

But it also can't be a later edge. Suppose our sequence of edges goes ..., e, f, ..., e', f, ...; e, e', f all have 0 on the left and 1 on the right, and f is the leftmost such edge after e and also after e'. That is, if you imagine pointing backwards along e and swinging your arm clockwise until it reaches f, it's always pointing into a 0-square when you do that; likewise with e',f. But if e,e' are not the same edge, one of those arm-swings must go past either e or e', which is impossible because each of those edges has 0 on one side and 1 on the other.

Here's part of a path, showing edges e,f. The arrow indicates the direction in which the path is traversed. Of course a real path has only horizontal and vertical edges; this is purely schematic.

The pink region is composed of 0-squares, because f was the leftmost-possible edge with 0 to the left and 1 to the right after e. The diagram would look qualitatively the same if we looked at e',f instead of e,f.

Here's what we get with e,e',f. In this diagram e' is to the right of e, but of course they could be either way around.

And the problem is that e lies strictly inside that 0-only region created by e',f, which is impossible because it needs to have 1 on its right. (If e were on the right and e' on the left, the problem would be that e' lies inside the 0-only region created by e,f.)