Move layerwise right, down,left, up
Intuition\n Describe your first thoughts on how to solve this problem. \nMove layerwise right, down, left, up.\n\nIt can solved by sorting according to max norm
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMove layerwise right, down, left, up.\n\nIt can solved by sorting according to max norm & angles with TC \n$O(rows\\times cols \\log (rows\\times cols))$ in a Math way; The distance to `(r0, c0)` w.r.t. max norm determines the layer.\n![layerwise.png](https://assets.leetcode.com/users/images/25a0f4b9-171d-4a35-9a62-314c9a51f2f0_1723084349.4281306.png)\n\n2nd C++ is subdividing ring into 4 parts.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Define a function `bool inside(int i, int j, int rows, int cols)` to judge whether (i, j) is inside within the grid.\n2. Find the layer by `layer=max({rows-r0, cols-c0, r0+1, c0+1})+1`\n3. `(r0, c0)` is the first one in `ans`\n4. Use a loop to proceed each layer` m=1..layer-1`\n5. Move (i, j) rightward with max step=2m-1, when (i, j) is inside the grid, add it to `ans`\n6. Move (i, j) downward with max step=2m-1, when (i, j) is inside the grid, add it to `ans`\n7. Move (i, j) leftward with max step=2m, when (i, j) is inside the grid, add it to `ans`\n8. Move (i, j) upward with max step=2m, when (i, j) is inside the grid, add it to `ans`\n9. `ans` is the \n10. 2nd C++ is given based subdividing ring into 4 parts. This solution is in fact implementing to sort the elements in a ring ( all elements in `ring[m]` has distance `m` to `(r0,c0)`); but after subdividing them into 4 parts, the ordering is very clear. Using deque to take care for pushing back or pushing front to keep the ordering, it doesn\'t need any procedure for sorting.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(layer^2)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(rows\\times cols)$$\n# Code\n```\nclass Solution {\npublic:\n    static bool inside(int i, int j, int rows, int cols){\n        return (i>=0)&&(i<rows)&&(j>=0)&&(j<cols);\n    }\n    static vector<vector<int>> spiralMatrixIII(int rows, int cols, int r0, int c0) \n    {\n        vector<vector<int>> ans(rows*cols);\n        ans[0]={{r0, c0}};\n        int layer=max({rows-r0, cols-c0, r0+1, c0+1})+1;\n        int i=r0, j=c0, k=1;\n        for(int m=1; m<layer; m++){\n            int di=0, dj=1, step=2*m-1;// rightward\n            for(int a=0; a<step; a++){\n                i+=di, j+=dj;\n                if (inside(i,j, rows, cols)) ans[k++]={{i, j}};\n            }\n            di=1, dj=0; //downward\n            for(int a=0; a<step; a++){\n                i+=di, j+=dj;\n                if (inside(i,j, rows, cols)) ans[k++]={{i, j}};\n            }\n            di=0, dj=-1;//leftward\n            step++; //increase step\n            for(int a=0; a<step; a++){\n                i+=di, j+=dj;\n                if (inside(i,j, rows, cols)) ans[k++]={{i, j}};\n            }\n            di=-1, dj=0; //upward\n            for(int a=0; a<step; a++){\n                i+=di, j+=dj;\n                if (inside(i,j, rows, cols)) ans[k++]={{i, j}};\n            }\n        }\n        return ans;\n    }\n};\n```\n# C++ subdividing ring[m] into 4 parts\n```\nclass Solution {\npublic:\n    static vector<vector<int>> spiralMatrixIII(int rows, int cols, int r0, int c0) {\n        vector<vector<int>> ans(rows*cols);\n        ans[0]={{r0, c0}};\n        int layer=max({rows-r0, cols-c0, r0+1, c0+1});\n        vector<array<deque<char>, 4>> ring(layer);//push_back or push_front\n        for(int i=0; i<rows; i++){\n            for(int j=0; j<cols; j++){\n                int d=max(abs(i-r0), abs(j-c0));\n                int region;\n                if (i==r0-d) ring[d][3].push_back(j);//rightward\n                else if (i-r0==d) ring[d][1].push_front(j);//leftward\n                else if (j-c0==-d) ring[d][2].push_front(i);//upward\n                else ring[d][0].push_back(i);//downward\n            }\n        }\n        int idx=1;\n        for(int m=1; m<layer; m++){\n            auto R=ring[m];\n            int sz=R[0].size();\n            for(int a=0; a<sz; a++) ans[idx++]={{R[0][a], m+c0}};\n            sz=R[1].size();\n            for(int a=0; a<sz; a++) ans[idx++]={{m+r0, R[1][a]}};\n            sz=R[2].size();\n            for(int a=0; a<sz; a++) ans[idx++]={{R[2][a], c0-m}};\n            sz=R[3].size();\n            for(int a=0; a<sz; a++) ans[idx++]={{ r0-m, R[3][a]}};\n        }\n        return ans;\n    }\n};\n```
['Array', 'Matrix', 'Simulation', 'C++']