{"id":3520,"date":"2018-08-13T14:05:08","date_gmt":"2018-08-13T21:05:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3520"},"modified":"2018-08-13T14:09:10","modified_gmt":"2018-08-13T21:09:10","slug":"leetcode-889-spiral-matrix-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-889-spiral-matrix-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 889. Spiral Matrix III"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

On a 2 dimensional grid with\u00a0R<\/code>\u00a0rows and\u00a0C<\/code>\u00a0columns, we start at\u00a0(r0, c0)<\/code>\u00a0facing east.<\/p>\n

Here, the north-west corner of the grid is at the\u00a0first row and column, and the south-east corner of the grid is at the last row and column.<\/p>\n

Now, we walk in a clockwise spiral shape to visit every position in this grid.<\/p>\n

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)<\/p>\n

Eventually, we reach all\u00a0R * C<\/code>\u00a0spaces of the grid.<\/p>\n

Return a list of coordinates representing the positions of the grid in the order they were visited.<\/p>\n

 <\/p>\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>R = 1<\/span>, C = 4<\/span>, r0 = 0<\/span>, c0 = 0<\/span>\r\nOutput: <\/strong>[[0,0],[0,1],[0,2],[0,3]]<\/span>\r\n\r\n\"\"\r\n<\/pre>\n
 <\/p>\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>R = 5<\/span>, C = 6<\/span>, r0 = 1<\/span>, c0 = 4<\/span>\r\nOutput: <\/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]]<\/span>\r\n\r\n\"\"\r\n\r\n<\/pre>\n
\n
\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= R <= 100<\/code><\/li>\n
  2. 1 <= C <= 100<\/code><\/li>\n
  3. 0 <= r0 < R<\/code><\/li>\n
  4. 0 <= c0 < C<\/code><\/li>\n<\/ol>\n
    Solution: Simulation<\/strong><\/h1>\n
    We can find out the moving sequence is ESWWNNEEESSSWWWWNNNN.<\/p>\n
    The pattern is 1,1,2,2,3,3,4,4,… steps in one direction, and turn right for 90 degrees.<\/p>\n
    directions are E,S,W,N,E,S,W,N…<\/p>\n
    Time complexity: O(max(R,C)^2)<\/p>\n
    Space complexity: O(1) or O(RC) if ans included.<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 52 ms\r\nclass Solution {\r\npublic:\r\n  vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {\r\n    vector<vector<int>> ans;\r\n    int k = 0;\r\n    int dirs[][2]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; \/\/ ESWN\r\n    int d = 0; \/\/ E\r\n    ans.push_back({r0, c0});\r\n    if (ans.size() == R * C) return ans;\r\n    while (++k) {\r\n      for (int i = 0; i < 2; ++i) {\r\n        for (int j = 0; j < k; ++j) {\r\n          c0 += dirs[d][0];\r\n          r0 += dirs[d][1];          \r\n          if (c0 < 0 || c0 >= C || r0 < 0 || r0 >= R) continue;\r\n          ans.push_back({r0, c0});\r\n          if (ans.size() == R * C) return ans;\r\n        }\r\n      d = (d + 1) % 4;\r\n      }\r\n    }\r\n    return {};\r\n  }\r\n};<\/pre>\n
     <\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem On a 2 dimensional grid with\u00a0R\u00a0rows and\u00a0C\u00a0columns, we start at\u00a0(r0, c0)\u00a0facing east. Here, the north-west corner of the grid is at the\u00a0first row and…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[216,177,179,375],"class_list":["post-3520","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-matrix","tag-medium","tag-simulation","tag-spiral","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3520","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3520"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3520\/revisions"}],"predecessor-version":[{"id":3524,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3520\/revisions\/3524"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}