The answer is negative. We show that for any $c < 2$ there exists some $N$ such that we can place $N$ mines (and select starting, ending cells) so that we need more than $cn+\mathcal O(1)$ rook moves to traverse from the starting cell to the ending one. We prove the following: (constructive) Claim: For any two positive integers $m, n \geq 2$ we can place mines on exactly $m(n+4)+2$ cells, select starting and ending cells, so that it takes at least $2m+(m-1)(2n-3)$ moves to go from the starting cell to the ending one. Proof: As they say, a diagram is worth a thousand words. This is a diagram when $m = n = 6$. The idea is to have $m$ upright chains containing $n$ mines, which alternate in "knight" move translations as shown. These are shown by the green mines. The blue mines depict how two consecutive chains (and of course, $S, E$) are connected. Note that by the way the space created between the mines is, every move is forced from $S$ until $E$ (here I forgot to close the grid in the diagram, but if we add two cells at $S, E$ and shift their locations one step up/down, we get the desired result). What remains is to count how many mines are used, and how many moves it takes. The number of green mines, is $mn$. The number of blue mines is $4m$ since exactly $4$ blue mines are contributed at each location where we shift from the previous chain to the next. Finally we add in the two random cells we need to close the grid. Note that as $m$ changes the number of green chains increases, whereas as $n$ increases the length of each green chain inrceases. The blue mines don't change their structure. We use $2$ moves per blue mine structure, which contributes $2m$ moves. On the other hand, for each of the $m-1$ spaces between two consecutive chains, we use $2n-3$ moves. This means that the total number of moves is $2m+(m-1)(2n-3)$ (IGNORE the part written in the image, I was being hasty there), proving the claim. $\square$ Now consider the above construction for fixed $m$ and note that $\frac{2m+(m-1)(2n-3)}{nm+4m+2)}$ limits to $\frac{2m-2}{m}$ as $n \mapsto \infty$. In particular, if there exists a $c$ for which we can always use at most $cn+\mathcal O(1)$ moves, we must have $c \geq \frac{2m-2}{m}$ for all $m \geq 2$. This clearly forces $c \geq 2$, solving this part of the problem.

We show that the answer to this part is yes. Suppose any $n$ mines are placed and we the minimum number of rook moves needed is $\ell$. Let the turning cells in the $\ell$-move path be $c_1, c_2, \dots, c_{\ell}$. Let $A$ be the number of columns containing at least one mine, define $B$ for rows analogously. Suppose that the rook is on some cell $c$. If it happens that irrespective of which direction is chosen, the rook cannot go on indefinitely, we call that cell $c$ locked. By (abuse of??) definition, we consider that mines are locked cells. Claim: If $1 \leq i < j \leq \ell$ are both unlocked, then $|i-j| \leq 5$. Proof: Draw a huge rectangular skeleton $\mathcal R$ encompassing all $n$ points. We show that the rook can go from $c_i$ to $c_j$ in less than $6$ moves, which is enough to force the bound above. First if the rook is on $c_i$, it moves to the cell on $\mathcal R$ in its open direction. Now note that the diameter of $\mathcal R$ in rook moves is $3$. In particular, in at most $3$ more moves the rook can go to the corresponding open intersection on $\mathcal R$ for cell $c_j$. After this the rook goes to $c_j$ again and the claim is proven. The claim has the very direct consequence that there are at most $6$ unlocked cells in the path $c_1, c_2, \dots, c_n$. The next claim is even more important: Claim: There are at most $AB$ locked cells. Proof: This is obvious since any locked cell lies in one of the $A$ columns and one of the $B$ rows. This allows us to conclude that $AB \geq n+\ell-6$. Now consider any one of the $A$ columns and suppose it contains $a$ mines. These $a$ mines divide the corresponding column into $a-1$ intervals, each of which is between two mines. Summing over all columns, there are $n-A$ such intervals. Consider the $n-B$ such intervals as well. Overall there are $2n-A-B$ such intervals. Finally, consider the (at most $6$) unlocked cells. These are allowed at most $2$ infinite/half infinite intervals, one for each direction. If one of the two directions does not have an unbounded interval, we add a dummy interval corresponding to it. All in all, we now have $2n-A-B+12$ such intervals. Label these $I_1, I_2, \dots, I_{k}$ in any order. Now note that for any two cells $c_i, c_{i+1}$ for $1 \leq i < \ell$ these two must be part of at least one interval $I_j$. Let $m_i$ denote such an index $j$ for $1 \leq i < \ell$. Claim: All the $m_i$s are distinct. Proof: Suppose otherwise. If $m_i = m_j$ for $1 \leq i < j < \ell$, then we can shorten the minimal path by traveling from $c_{i}$ to $c_{j+1}$ directly. $\square$ With all the above claims, we are ready to kill this problem. Since all the $m_i$ are distinct, we have \[2n-A-B+12 \geq \ell-1\]Now since $AB \geq n+\ell-6$ which implies from AM-GM that $A+B \geq 2\sqrt{n+\ell-6}$. This gets us the bound \[2n-2\sqrt{n+\ell-6} \geq \ell-13\]We obtain that \[(2n-\ell+13)^2 \geq 4(n+\ell-6)\]which Wolfram tells me is the same as \[\ell \leq 2n-2\sqrt{3n+8}+15\]It is not too difficult to check that the above is $\leq 2n-2\sqrt{3n}+100$ for all $n \geq 1$, thereby solving the problem.

Construction highly motivated by "what bishop does fast rook can't do fast". I know the very enlightened among you will think very hard about what happens if $n+\ell \leq 5$ since then we cannot take square roots at all! I assure you, this error is of insignificant importance, the constant term $100$ hard carries. checkm8 nitpickers