Solution
Approach 1: Walk in a Spiral
Intuition
We can walk in a spiral shape from the starting square, ignoring whether we stay in the grid or not. Eventually, we must have reached every square in the grid.
Algorithm
Examining the lengths of our walk in each direction, we find the following pattern: 1, 1, 2, 2, 3, 3, 4, 4, ...
That is, we walk 1 unit east, then 1 unit south, then 2 units west, then 2 units north, then 3 units east, etc. Because our walk is selfsimilar, this pattern repeats in the way we expect.
After, the algorithm is straightforward: perform the walk and record positions of the grid in the order we visit them. Please read the inline comments for more details.
Complexity Analysis

Time Complexity: . Potentially, our walk needs to spiral until we move in one direction, and in another direction, so as to reach every cell of the grid.

Space Complexity: , the space used by the answer.
Analysis written by: @awice.