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

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define EPS 1e-10
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}
ll dx[]={0, 1, 0, -1};
ll dy[]={1, 0, -1, 0};

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<ll> >matrix(rows + 2, vector<ll>(cols + 2, 0));
        rep(i, matrix.size()){
            rep(j, matrix[i].size()){
                if(i == 0 or i == matrix.size() - 1 or j == 0 or j == matrix[0].size() - 1){
                    matrix[i][j] = -1;
                }
            }
        }
        ll n = 1;
        ll x = rStart + 1, y = cStart + 1;
        ll idx = 3;
        while(true){
            if(n > rows * cols) break;

            if(matrix[x][y] == 0){
                matrix[x][y] = n;
                n ++;
            }

            ll nx = x + dx[idx];
            ll ny = y + dy[idx];

            ll cx = x + dx[(idx + 1) % 4];
            ll cy = y + dy[(idx + 1) % 4];


            // rep(i, matrix.size()){
            //     rep(j, matrix[i].size()){
            //         if(i == x and j == y) cout << "x";
            //         else if(matrix[i][j] == -1) cout << "#";
            //         else if(matrix[i][j] == 0) cout << ".";
            //         else cout << matrix[i][j];
            //     }
            //     cout << endl;
            // }
            // cout << "next: " << nx << ", " << ny << endl;
            // cout << "cour: " << cx << ", " << cy << " is " << matrix[cx][cy] << endl;

            // cout << "-------------------------" << endl;

            if(matrix[cx][cy] <= 0){
                x = cx, y = cy;
                idx ++; idx %= 4;
            }else{
                x = nx, y = ny;
            }
        }

        vector<vector<int> > ans(rows * cols, vector<int>(2, 0));
        rep(i, matrix.size()){
            rep(j, matrix[i].size()){
                if(matrix[i][j] != -1){
                    ans[matrix[i][j] - 1][0] = i - 1;
                    ans[matrix[i][j] - 1][1] = j - 1;
                }
            }
        }
        return ans;
    }
};
13100