Ma phương trong lưới trong C++

Mô tả bài toán

Cho lưới số nguyên, đếm số ma phương 3×3 con. Ma phương 3×3 là lưới chứa các số khác nhau từ 1-9, tổng mỗi hàng, cột, đường chéo bằng nhau.

Ví dụ: Lưới 3×4 chứa 1 ma phương tại góc trên trái.

Giải pháp (Kiểm tra 8 mẫu cố định)

• Chỉ có 8 ma phương 3×3 duy nhất (tính đối xứng).
• Mã hóa mỗi ma phương 3×3 thành số 9 chữ số (duyệt hàng).
• Duyệt mọi vị trí tâm 3×3 trong lưới, mã hóa và kiểm tra có trong tập 8 mẫu không.

Ví dụ minh họa

#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[9][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[0].size(); j++) {
                int sum = 0;
                for (int k = 0; k < 9; k++) {
                    sum = sum * 10 + 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);
    return 0;
}

Đầu vào

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

Đầu ra

1