<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 {
public:
    int row, col;

    bool isValid(int row, int col, int rows, int cols) {
        return row >= 0 && col >= 0 && row < rows && col < cols;
    }

    void helper(vector<vector<int>>& ans, vector<vector<int>>& dirs, int step, int rows, int cols) {
        row += dirs[0][0];
        col += dirs[0][1];

        // Go right 1 time.
        if(isValid(row, col, rows, cols)) {
            ans.push_back({row, col});
            if(ans.size() == rows*cols) return;
        }

        // Go bottom step + 1 time.
        for(int i=0; i<step*2-1; i++) {
            row += dirs[1][0];
            col += dirs[1][1];

            if(isValid(row, col, rows, cols)) {
                ans.push_back({row, col});
                if(ans.size() == rows*cols) return;
            }
        }

        // Go left step + 2 time.
        for(int i=0; i<step*2; i++) {
            row += dirs[2][0];
            col += dirs[2][1];

            if(isValid(row, col, rows, cols)) {
                ans.push_back({row, col});
                if(ans.size() == rows*cols) return;
            }
        }

        
        // Go up step + 2 time.
        for(int i=0; i<step*2; i++) {
            row += dirs[3][0];
            col += dirs[3][1];

            if(isValid(row, col, rows, cols)) {
                ans.push_back({row, col});
                if(ans.size() == rows*cols) return;
            }
        }

        // Go right step + 2 time.
        for(int i=0; i<step*2; i++) {
            row += dirs[0][0];
            col += dirs[0][1];

            if(isValid(row, col, rows, cols)) {
                ans.push_back({row, col});
                if(ans.size() == rows*cols) return;
            }
        }        
    }

    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        // ->, down, <-, up
        vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<vector<int>> ans;
        int mx = 10000;

        row = rStart;
        col = cStart;
        ans.push_back({row, col});

        for(int step = 1; step <= 105; step++) {
            if(ans.size() < rows*cols) {
                helper(ans, dirs, step, rows, cols);
            } else {
                break;
            }
        }

        return ans;
    }
};
14500