มาจิกสแควร์ในกริดใน C++

ปัญหา

สมมติว่าเรามีกริด เราต้องหาจำนวนเซิร์บกริดมาจิกสแควร์ในกริดนั้น มาจิกสแควร์คือกริด 3 x 3 ที่เติมด้วยตัวเลขที่ไม่ซ้ำกันจาก 1 ถึง 9 โดยที่แต่ละแถว คอลัมน์ และทั้งสองเส้นทแยงมุมมีผลรวมเท่ากัน

เช่น ถ้าผนวกเข้าเป็น

วิธีแก้ปัญหา

1. กำหนดเซ็ตหนึ่งอันมีค่า: [816357492, 834159672, 618753294, 672159834, 492357816, 438951276, 294753618, 276951438]
2. กำหนดอาร์เรย์ offset ขนาด 9 x 2 := {{-2,-2},{-2,-1},{-2,0},{-1,-2},{-1,-1},{-1,0},{0,-2},{0,-1},{0,0}}
3. ans := 0
4. for i := 2 ถึง จำนวนแถวของกริด - 1 ทำ:
   • for j := 2 ถึง จำนวนคอลัมน์ของกริด - 1 ทำ:
     • sum := 0
     • for k := 0 ถึง 8 ทำ:
       • sum := sum * 10
       • sum := sum + grid[i + offset[k][0]][j + offset[k][1]]
     • ans := ans + จำนวนครั้งที่ sum อยู่ใน s
5. คืนค่า ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int numMagicSquaresInside(vector<vector<int>>& grid) { 
        const unordered_set<int> s{816357492, 834159672, 618753294, 
            672159834,492357816, 438951276, 294753618,276951438}; 
        const int offset[][2] = {{-2, -2}, {-2, -1}, {-2, 0},{-1, -2}, {-1, -1}, {-1, 0}, { 0, -2}, { 0, -1}, { 0, 0}}; 
        int ans = 0; 
        for(int i = 2; i < grid.size(); i++) 
        { 
            for(int j = 2; j < grid.size(); j++) 
            { 
                int sum = 0; 
                for(int k = 0; k < 9; k++) 
                { 
                    sum *= 10; 
                    sum += grid[i + offset[k][0]][j+offset[k][1]]; 
                } 
                ans += s.count(sum); 
            } 
        } 
        return ans; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{4,3,8,4},{9,5,1,9},{2,7,6,2}}; 
    cout << (ob.numMagicSquaresInside(v)); 
}

อินพุต

{{4,3,8,4},{9,5,1,9},{2,7,6,2}}

เอาต์พุต

1