Let us denote $m := \lfloor\sqrt{n}/2\rfloor$. Let the colors be $\{1,2,\dots,n\}$ For any color $i\,,\, i=1,2,\dots,n$, let $S_i$ be the set of squares, colored in "$i$". For every cell $s\in S_i$ , denote by $B(s,m)$ the square with center in $s$ and side length $2m-1$. Denote also $B(S_i, m) := \bigcup_{s\in S_i} B(s,m)$. The idea is to show there are four sets among $B(S_i,m),i=1,2,\dots,n$ that meet at common point(cell). If this cell is $x$, then the square with centre $x$ and side length $2m-1\leq \sqrt{n}$ would contain four different colors. To show it, let us estimate $|B(S_i, m)|$. Intuitively,$|B(S_i, m)|$ is minimal when $S_i$ is as "compact" as possible, that's when $S_i$ is a square(or close to it) with side length $\lfloor \sqrt{n} \rfloor$. In that case $B(S_i, m)$ is a square with side length $\lfloor \sqrt{n} \rfloor+2m-2\geq 2\sqrt{n}-3$. It means $|B(S_i, m)|\geq 4n-12\sqrt{n}-9$. For now being let us drop the rigorous proof of this estimate. Further, all that sets $B(S_i, m)$ are inside a square $Q$ with side length $n+2m-2$, with number of cells: $(n+2m-2)^2=n^2+4m^2+4+4mn-4n-8m<n^2 + 5n\sqrt{n}$. It is easy to see $\sum_{i=1}^n |B(S_i, m)|> 3\cdot|Q|$, which implies at least four among the sets $B(S_i, m)$ have a common point.

Quote: $|B(S_i, m)|$ is minimal when $S_i$ is as "compact" as possible It's not obvious for me .Can you prove it,please?

Yes, it was not a clear explanation. It was only a hint what to seek for. In fact we need an estimate like $|B(S_i, m)|\geq c\cdot n$ for some constant $c>3$ and big enough $n$. Let us project the set $S_i$ (the cells colored in the $i$-th color) onto $x$ and $y$ axis and see how many elements these two projections may have. Let $k$ be the maximal number of cells from $S_i$ contained in one and the same column. Thus, the number of columns containing at least one cell in $S_i$ is at least $|S_i|/m$. Hence the total "length" of that projections is at least $m+|S_i|/m\geq 2\sqrt{|S_i|}=2\sqrt{n}$. For each column that contains at least one cell in $S_i$ let $c_h$ and $c_{\ell}$ be the highest and lowest among that cells (they may coincide). Then all $m-1$ cells above $c_h$ and $m-1$ cells bellow $c_{\ell}$ belong to $B(S_i, m)$. Similarly, for the rows that contain at least one element from $S_i$, let $c_{l}, c_r$ be the leftmost/rightmost cell among that ones, then $m-1$ cells to the left of $c_l$ and $m-1$ cells to the right of $c_r$ belong to $B(S_i, m)$. Thus, $B(S_i, m)$ consists of at least $4\sqrt{n}\cdot (m-1)$ cells. Adding the cells in $S_i$ itself, which are exactly $n$, we can estimate that $|B(S_i, m)|$ is at least something like $3n$. Now, among all the cells of $S_i$, which are at the bottom, let $c_{b,l}, c_{b,r}$ be the leftmost and rightmost ones (they may coincide). Then the south-west quarter of $B(c_{b,l}, m)$ and south-east quarter of $B(c_{b,r}, m)$ also belong to $B(S_i, m)$. In the similar way we proceed with the top cells of $S_i$. Thus, we add additionally something about $n$ cells and obtain $|B(S_i, m)|\geq c\cdot n$, where $c$ is slightly bellow $4$.

Now it is clear. Thank you