Ant Riddle

Prompt

An ant plays a game on a board with 1000 rows and 999 columns. There are trap doors in 998 of the cells. Initially, the ant does not know where any of the trap doors are, but it knows that there is exactly trap door in each row except the first row and the last row, and that each column contains at most one trap door. The ant makes a series of attempts to go from the first row to the last row. On each attempt, it chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (It is allowed to return to a previously visited cell.) If it reaches a cell with a trap door, its attempt ends and it is transported back to the first row to start a new attempt. The ant remembers whether or not each cell it has visited contains a trap door. If it reaches any cell in the last row, its attempt ends and the game is over. Determine the minimum value of n for which the ant has a strategy that guarantees reaching the last row on the nth attempt or earlier, regardless of the locations of the trap doors.