<p>You start at the cell <code>(rStart, cStart)</code> of an <code>rows x cols</code> grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.</p>

<p>You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid&#39;s boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all <code>rows * cols</code> spaces of the grid.</p>

<p>Return <em>an array of coordinates representing the positions of the grid in the order you visited them</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/24/example_1.png" style="width: 174px; height: 99px;" />
<pre>
<strong>Input:</strong> rows = 1, cols = 4, rStart = 0, cStart = 0
<strong>Output:</strong> [[0,0],[0,1],[0,2],[0,3]]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/24/example_2.png" style="width: 202px; height: 142px;" />
<pre>
<strong>Input:</strong> rows = 5, cols = 6, rStart = 1, cStart = 4
<strong>Output:</strong> [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rows, cols &lt;= 100</code></li>
	<li><code>0 &lt;= rStart &lt; rows</code></li>
	<li><code>0 &lt;= cStart &lt; cols</code></li>
</ul>

inline const auto optimize = []() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  return 0;
}();


class Solution {
    using POS = std::complex<int>;

public:
    static constexpr std::vector<std::vector<int>> spiralMatrixIII(int rows, int cols, int rStart,
                                        int cStart) {
        // ok, this sounds sorta fun actually, I will implement this as one of
        // those old turtle apis.
        std::vector<std::vector<int>> out(rows * cols, {0, 0});
        int outIdx = 0;
        const int N = rows * cols;


        // Our little turtle class.
        POS dir{1, 0};
        POS pos{cStart, -rStart};

        const auto turnRight = [&]() { dir *= POS{0, -1}; };
        // const auto turnRight = [&]() { dir *= POS{0, 1}; };
        
        const auto walkForward = [&](const int steps) -> bool {
            if (N <= outIdx) {
                return true;
            }

            for (int i = 0; i < steps; i++) {
                pos += dir;
                if (0 <= pos.real() && pos.real() < cols && -rows < pos.imag() &&
                    pos.imag() <= 0) {
                    out[outIdx++] = {-pos.imag(), pos.real()};
                    if (outIdx == N)
                        return true;
                }
            }

            return false;
        };

        out[outIdx++] = {-pos.imag(), pos.real()};

        walkForward(1);
        turnRight();
        if(walkForward(1))
            return out;

        // ok, now we are in the corner.
        int width = 2;
        while (true) {
            // std::cout << "We are now standing in: " << pos.real() << ", " << pos.imag() << ", width=" << width << "\n";
            // OK, now we are in a corner facing down.
            turnRight();
            walkForward(width);
            turnRight();
            walkForward(width);
            turnRight();
            walkForward(width+1);
            turnRight();

            if (walkForward(width+1))
                break;

            width += 2;
        }

        return out;
    }
};
12900