Denote each cell with coordinate $(a,b) \; (a,b \in \mathbf{N})$ starting from the bottom left cell with coordinate $(1,1)$. Notice that the equality holds when the cells are coloured diagonally as in the chessboard starting from $(1,1)$. In this configuration, notice that the set of cells arranged diagonally is set of coordinates $(x,y)$ with $x+y$ is constant. Hence, denote $k$-th diagonal line as set of cells $(x,y)$ so $x+y=k$. Claim 1. If we have $k$ coloured cells on some $m$-th diagonal line then there are at least $k+1$ neighbour cells $(a,b)$ of those $k$ cells such that $a+b>m$. We call such cells upper neighbour cells. One can observe that the upper neighbour cells of coloured cells in $k$-th diagonal line lie on $(m+1)$-th diagonal line. Therefore, the sets of upper neighbour cells in any two distinct diagonal lines are disjoint. For example, in figure below, the upper neighbour cells of blue cells on $5$-th diagonal line are the red cells on $6$-th diagonal line. [asy][asy] import graph; size(4cm); for (int i=0; i<=6; i=i+1) { draw((0,i)--(6,i)^^(i,0)--(i,6)); } for (int i=0; i<=5;i=i+1){ for (int j=0; j<=5;j=j+1){ if ( ((i+j)%2==0)&&(i+j<=5) ) { fill((i,j)--(i,j+1)--(i+1,j+1)--(i+1,j)--cycle,blue); } } } for (int i=0;i<=5;i=i+1){ fill((i,6-i)--(i,5-i)--(i+1,5-i)--(i+1,6-i)--cycle,red); } [/asy][/asy] We proceed by induction on $n$. Among $n^2$ coloured cells, we take out $2n-1$ coloured cells (call it red cells) of coordinate $(a,b)$ in following steps: Take out cells $(x,y)$ in descending order of $x+y$. Among the cells $(x,y)$ with $x+y=k$, take out cells in descending order of $y$. After this, we left with $(n-1)^2$ coloured cells (call it blue cells) which will have $(n-1)^2+(n-1)$ neighbour cells. Let $S_{n-1}$ be set of neighbour cells for these $(n-1)^2$ blue cells. Suppose $2n-1$ red cells lie on $h$ diagonal lines starting from $k$-th diagonal line to $(k+h-1)$-th diagonal line. Denote $a_i$ as number of red cells in $i$-th diagonal line. From the claim, we find that there will be no blue cells on $i$-th diagonal line where $k<i\le k+h-1$. Therefore, the $a_i$ cells on $i$-th diagonal line ($k<i\le k+h-1$) will contribute at least $a_i+1$ neighbour cells to the total $|S_n|$ (not including neighbour cells $S_{n-1}$ of blue cells). For $a_k$ red cells on $k$-th diagonal line, if there is no blue cells on $k$-th diagonal line then we will have extra $a_k+1$ neighbour cells added to $S_n$. However, if there is at least one blue cell then from the second requirement in the algorithm, the blue cells will have at most one common upper neighbour cell with such $a_k$ red cells, which results in extra $a_k$ neighbour cells added to $S_n$ (not including neighbour cells $S_{n-1}$ of blue cells) (see below diagram) . [asy][asy] import graph; size(4cm); for (int i=0; i<=7; i=i+1) { draw((0,i)--(7,i)^^(i,0)--(i,7)); } for (int i=0;i<=4;i=i+1){ fill((i,6-i)--(i,5-i)--(i+1,5-i)--(i+1,6-i)--cycle,red); } fill((5,1)--(5,0)--(6,0)--(6,1)--cycle,blue); [/asy][/asy] From these observation, since $\sum_{i=k}^{k+h-1}a_i=2n-1$ so if either no blue cell on $k$-th diagonal line or $h \ge 2$ then \[S_n \ge S_{n-1}+\sum_{i=k}^{k+h-1}a_i+h-2=n^2+n+h-2 \ge n^2+n.\]If $h=1$ then that means all $2n-1$ cells plus at least one blue cell can be put on $k$-th diagonal line. Hence, $k \ge 2n$ and this last $k$-th diagonal line contains at least $2n$ coloured cells. Denote $b_i$ as number of coloured cells on $i$-th diagonal line then $b_k \ge 2n$. It's not hard to show that for $2 \le i \le k$, number of neighbour cells on $i$-th diagonal line is at least $(b_{i-1}+b_{i+1})/2$. Note that $b_{k+1}=0$ and the $(k+1)$-th diagonal line has at least $b_k+1 \ge 2n+1$ neighbour cells. Therefore, \begin{align*} |S_n| & \ge \sum_{i=2}^{k}\frac{b_{i-1}+b_{i+1}}{2}+b_k+1 , \\ &= \sum_{i=1}^{k}b_i+\frac 12(b_{k}-b_1)+1, \\ &= n^2+\frac 12 (b_{k}-b_1)+1, \\ & > n^2+n. \end{align*}

Very fast solution! Call a cell good if at least one of its neighbors is colored. Claim: If on a line/column there are $k>0$ colored cells, there are at least $k+1$ good cells. Proof: We say that cell $a$ is impressed by cell $b$ if $b$ is colored and is a neighbour of $a.$ Every colored cell has two neighbors and thus, generates two impressions, so there is a total of $2k$ impressions. Assume there are $t$ good cells. It is easy to observe that the left-most and right-most good cells are only impressed once and, in general, a good cell can be impressed at most twice. Therefore, the maximal number of impressions is $2+2(t-2)=2t-2$ so we have $2t-2\geq 2k\iff t\geq k+1$ completing the proof. Now, let $C$ and $L$be the set of columns and lines respectively that have at least one colored cell. For each $C_i\in C,$ let $c_i$ denote the number of colored cells on $C_i$ and define $l_i$ similarly. Finally, let $N$ be the total amount of good cells. Then, using our claim, \[2N\geq\sum_{C_i\in C}(c_i+1)+\sum_{L_i\in L}(l_i+1)=2n^2+|C|+|L|.\]Since there are $n^2$ colored cells, then by the pigeonhole principle, on some line there must be at least $n^2/|L|$ points, which determine $n^2/|L|$ different columns, with at least one colored point each. Therefore, $|C|\geq n^2/|L|$ so $|C|+|L|\geq n^2/|L|+|L|$ and by am-gm it is $\geq 2n.$ By plugging this in the latter, we get that $2N\geq 2n^2+2n$ which, upon division by two, gives us the desired, $N\geq n^2+n.$

FTSOC assume that the problem statement doesn't hold.We shall prove that we either have $2n$ rows(or columns) , or we have $n$ different diagonals. But before that , we'll show that both of this claims solve the problem and give us $n^2 + n$ different "marked" squares.Let the left-most column of the coordinate system be $l$ Consider the case we have $2n$ rows Note that each row with $k$ colored cells add us $k+1$ marked squares JUST by adjacently in itself , unless the left-most colored lies on $l$ and the cells are alternatively colored (which implies , the hole block length is $2k$ ). But considering the left-most cell of these rows , which were on $l$ , there are at most $n$ of them by considering the adjacently on $l$. Also , if there were $n$ other rows , we can consider the left cell of the left-most cell of these rows which give us our $n^2 + n$ marked cells. So there are at most $2n-1$ rows and similarly $2n-1$ columns. Now , Consider the case we have $n$ diagonals(each cell in them have fix $x+y$). Now considering the "Right-adjacently" of each cell and "Up-adjacently" of the up-most cell of each diagonal we're done. So let there be $2n-1$ rows and $2n-1$ columns(clearly it's enough to show that there are $n$ different diagonals in this case). So the coordinate of each $n^2$ colored cell is in form $(a_i , b_j)$ between $2n-1$ pair-wise distinct integers $a_1 , a_2 ,..., a_{2n-1}$ and $2n-1$ pair-wise distinct integers $b_1 , b_2 ,..., b_{2n-1}$. Now consider all $n^2$ sums $a_i + b_j$ of these $n^2$ colored squares. Now it's clear that if $a_i + b_j = a_k + b_l$ for two different pair of points , then we cannot have either $i=k$ or $j=l$ $*$. now by PPH there are two indices , for example 1,2 , such that $n$ points have the x-coordinate $a_1$ or $a_2$ and their represented sums are distinct. Similarly there exists such $b_1$ and $b_2$. now between all $\ge 2n$ sums containing this 4 numbers , a value can be represented in at most two ways with these $2n$ sums , since otherwise $*$ won't hold. So there is at least $n$ different values between this sums and we're done.