[C++/Java/Python] 1,1,2,2,3,3 Steps
Intuition:\nTake steps one by one.\nIf the location is inside of grid, add it to res.\nBut how to simulate the path?\n\nIt seems to be annoying, but if we obser
## **Intuition**:\nTake steps one by one.\nIf the location is inside of grid, add it to `res`.\nBut how to simulate the path?\n\nIt seems to be annoying, but if we observer the path:\n\nmove right `1` step, turn right\nmove down `1` step, turn right\nmove left `2` steps, turn right\nmove top `2` steps, turn right,\nmove right `3` steps, turn right\nmove down `3` steps, turn right\nmove left `4` steps, turn right\nmove top `4` steps, turn right,\n\nwe can find the sequence of steps: 1,1,2,2,3,3,4,4,5,5....\n\nSo there are two thing to figure out:\n1. how to generate sequence 1,1,2,2,3,3,4,4,5,5\n2. how to turn right?\n<br>\n\n## **Generate sequence 1,1,2,2,3,3,4,4,5,5**\nLet `n` be index of this sequence.\nThen `A0 = 1`, `A1 = 1`, `A2 = 2` ......\nWe can find that `An = n / 2 + 1`\n<br>\n\n## **How to turn right?**\nBy cross product:\nAssume current direction is (x, y) in plane, which is (x, y, 0) in space.\nThen the direction after turn right (x, y, 0) \xD7 (0, 0, 1) = (y, -x, 0)\nTranslate to code: `tmp = x; x = y; y = -tmp;`\n\nBy arrays of arrays:\nThe directions order is (0,1),(1,0),(0,-1),(-1,0), then repeat.\nJust define a variable.\n<br>\n\n## **Time Complexity**:\nTime `O(max(R,C)^2)`\nSpace `O(R*C)` for output\n<br>\n\n**Java:**\n```java\n    public int[][] spiralMatrixIII(int R, int C, int x, int y) {\n        int[][] res = new int[R * C][2];\n        int dx = 0, dy = 1, n = 0, tmp;\n        for (int j = 0; j < R * C; ++n) {\n            for (int i = 0; i < n / 2 + 1; ++i) {\n                if (0 <= x && x < R && 0 <= y && y < C)\n                    res[j++] = new int[] {x, y};\n                x += dx;\n                y += dy;\n            }\n            tmp = dx;\n            dx = dy;\n            dy = -tmp;\n        }\n        return res;\n    }\n```\n**C++:**\n```cpp\n    vector<vector<int>> spiralMatrixIII(int R, int C, int r, int c) {\n        vector<vector<int>> res = {{r, c}};\n        int dx = 0, dy = 1, tmp;\n        for (int n = 0; res.size() < R * C; n++) {\n            for (int i = 0; i < n / 2 + 1; i++) {\n                r += dx, c += dy;\n                if (0 <= r && r < R && 0 <= c && c < C)\n                    res.push_back({r, c});\n            }\n            tmp = dx, dx = dy, dy = -tmp;\n        }\n        return res;\n    }\n```\n**Python:**\n```python\n    def spiralMatrixIII(self, R, C, x, y):\n        res = []\n        dx, dy, n = 0, 1, 0\n        while len(res) < R * C:\n            for i in xrange(n / 2 + 1):\n                if 0 <= x < R and 0 <= y < C:\n                    res.append([x, y])\n                x, y = x + dx, y + dy\n            dx, dy, n = dy, -dx, n + 1\n        return res\n```\n
[]