A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers\u00a0from 1 to 9<\/strong>\u00a0such that each row, column, and both diagonals all have the same sum.<\/p>\n Given an\u00a0 Example 1:<\/strong><\/p>\n Note:<\/strong><\/p>\n Time complexity: O(m*n)<\/p>\n Space complexity: O(1)<\/p>\n C++<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" Problem A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers\u00a0from 1 to 9\u00a0such that each row, column, and…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[222,31,216],"class_list":["post-3025","post","type-post","status-publish","format-standard","hentry","category-array","tag-easy","tag-math","tag-matrix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3025","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=3025"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3025\/revisions"}],"predecessor-version":[{"id":3027,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3025\/revisions\/3027"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3025"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3025"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3025"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}grid<\/code>\u00a0of integers, how many 3 x 3 “magic square” subgrids are there?\u00a0 (Each subgrid is contiguous).<\/p>\nInput: <\/strong>[[4,3,8,4],\r\n [9,5,1,9],\r\n [2,7,6,2]]\r\nOutput: <\/strong>1\r\nExplanation: <\/strong>\r\nThe following subgrid is a 3 x 3 magic square:\r\n438\r\n951\r\n276\r\n\r\nwhile this one is not:\r\n384\r\n519\r\n762\r\n\r\nIn total, there is only one magic square inside the given grid.\r\n<\/pre>\n
\n
1 <= grid.length\u00a0<= 10<\/code><\/li>\n1 <= grid[0].length\u00a0<= 10<\/code><\/li>\n0 <= grid[i][j] <= 15<\/code><\/li>\n<\/ol>\nSolution<\/h1>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 0 ms\r\nclass Solution {\r\npublic:\r\n int numMagicSquaresInside(vector<vector<int>>& grid) {\r\n int m = grid.size();\r\n int n = grid[0].size();\r\n int ans = 0;\r\n for (int i = 0; i < m - 2; ++i)\r\n for (int j = 0; j < n - 2; ++j)\r\n ans += magic(grid, j, i);\r\n return ans;\r\n }\r\nprivate:\r\n int magic(const vector<vector<int>>& grid, int x, int y) {\r\n vector<int> rows(3);\r\n vector<int> cols(3);\r\n vector<int> exps{15, 15, 15};\r\n int dig = 0;\r\n for (int i = 0; i < 3; ++i)\r\n for (int j = 0; j < 3; ++j) {\r\n int v = grid[y + i][x + j];\r\n if (v <= 0 || v > 9) return 0; \/\/ must between 1 and 9\r\n rows[i] += v;\r\n cols[j] += v;\r\n if (i == j) dig += v;\r\n }\r\n return rows == exps && cols == exps && dig == 15;\r\n }\r\n};<\/pre>\n