Problem
A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).
Example 1:
Input: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
438
951
276
while this one is not:
384
519
762
In total, there is only one magic square inside the given grid.
Note:
1 <= grid.length <= 101 <= grid[0].length <= 100 <= grid[i][j] <= 15
Solution
Time complexity: O(m*n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua // Running time: 0 ms class Solution { public: int numMagicSquaresInside(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); int ans = 0; for (int i = 0; i < m - 2; ++i) for (int j = 0; j < n - 2; ++j) ans += magic(grid, j, i); return ans; } private: int magic(const vector<vector<int>>& grid, int x, int y) { vector<int> rows(3); vector<int> cols(3); vector<int> exps{15, 15, 15}; int dig = 0; for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) { int v = grid[y + i][x + j]; if (v <= 0 || v > 9) return 0; // must between 1 and 9 rows[i] += v; cols[j] += v; if (i == j) dig += v; } return rows == exps && cols == exps && dig == 15; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment