Re: [閒聊] 每日leetcode
看板Marginalman作者smart0eddie (smart0eddie)時間1年前 (2024/08/09 11:22)推噓0(0推 0噓 0→)留言0則, 0人參與討論串681/1548 (看更多)
2024-08-09
840. Magic Squares In Grid
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 a row x col grid of integers, how many 3 x 3 contiguous magic square
subgrids are there?
Note: while a magic square can only contain numbers from 1 to 9, grid may
contain numbers up to 15
我只會暴力解
醜死
可是跑起來好快
Compiler做了甚麼事
class Solution {
public:
int numMagicSquaresInside(vector<vector<int>>& grid) {
if (grid.size() < 3 || grid[0].size() < 3) {
return 0;
}
int count = 0;
for (int r = 1; r < grid.size() - 1; ++r) {
for (int c = 1; c < grid[0].size() - 1; ++c) {
if (isMagic(r, c, grid)) {
count++;
}
}
}
return count;
}
private:
bool isMagic(int r, int c, vector<vector<int>>& grid) {
if (5 != grid[r][c]) {
return false;
}
if (15 != grid[r-1][c-1] + grid[r-1][c] + grid[r-1][c+1]) {
return false;
}
if (10 != grid[r][c-1] + grid[r][c+1]) {
return false;
}
if (15 != grid[r+1][c-1] + grid[r+1][c] + grid[r+1][c+1]) {
return false;
}
if (15 != grid[r-1][c-1] + grid[r][c-1] + grid[r+1][c-1]) {
return false;
}
if (10 != grid[r-1][c] + grid[r+1][c]) {
return false;
}
if (15 != grid[r-1][c+1] + grid[r][c+1] + grid[r+1][c+1]) {
return false;
}
if (10 != grid[r-1][c-1] + grid[r+1][c+1]) {
return false;
}
if (10 != grid[r-1][c+1] + grid[r+1][c-1]) {
return false;
}
vector<int> counter(10);
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
if (grid[r+i][c+j] > 9) {
return false;
}
if (counter[grid[r+i][c+j]]) {
return false;
}
counter[grid[r+i][c+j]]++;
}
}
return true;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723173748.A.67E.html
討論串 (同標題文章)
完整討論串 (本文為第 681 之 1548 篇)：