<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>

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        # treat each straight run of cells in each direction separately
        def right():
            P = [rStart, cStart]
            for i in count(1, 2):
                if P[0] < 0:
                    break
                #print('right', end=' ')
                yield ((P[0], c) for c in range(max(0, P[1]), min(P[1]+i, cols)))
                P = P[0]-1, P[1]-1
        def down():
            P = [rStart, cStart+1]
            for i in count(1, 2):
                if P[1] >= cols:
                    break
                #print('down', end=' ')
                yield ((r, P[1]) for r in range(max(0, P[0]), min(P[0]+i, rows)))
                P = P[0]-1, P[1]+1
        def left():
            P = [rStart+1, cStart+1]
            for i in count(2, 2):
                if P[0] >= rows:
                    break
                #print('left', end=' ')
                yield ((P[0], c) for c in range(min(cols-1, P[1]), max(-1, P[1]-i), -1))
                P = P[0]+1, P[1]+1
        def up():
            P = [rStart+1, cStart-1]
            for i in count(2, 2):
                if P[1] < 0:
                    break
                #print('up', end=' ')
                yield ((r, P[1]) for r in range(min(rows-1, P[0]), max(-1, P[0]-i), -1))
                P = P[0]+1, P[1]-1
        Q = deque((right(), down(), left(), up()))
        #out = []
        while Q:
            D = Q.popleft()
            n = next(D, None)
            if n:
                #n = list(n)
                #print(n)
                #out.extend(n)
                yield from n
                Q.append(D)
        #return out
17100