Construction

• fill the first row entirely with R;

• fill the last row entirely with B;

• make every intermediate row identical: RBRB....

Every column contains a red cell in the first row and a blue cell in the last row. Every red cell in an intermediate row is vertically connected to the first row, so all red cells are connected. Similarly, every blue cell is connected to the last row.

In every pair of adjacent columns, an intermediate row contains both colors. Hence every $2\times 2$ square between intermediate rows contains both colors, and the same is true at the borders with the first and last rows. For $n=2$, one all-red row and one all-blue row form a valid construction as well.

Complexity

The output has $n^2$ characters, so the time is O(n^2) and the extra memory is $O(n)$.