一 🏠 题目描述
840. 矩阵中的幻方
3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
示例 1：
输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2] 输出: 1解释: 下面的子矩阵是一个 3 x 3 的幻方： 而这一个不是： 总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
示例 2:
输出: grid = [[8]] 输入: 0
提示:
row == grid.length col == grid[i].length 1 <= row, col <=100 <= grid[i][j] <=15
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎
3 x 3 幻方是一个 从 1 到 9 不同数字的 3 x 3 矩阵，每行每列及两条对角线上各数之和都相等。给一个矩阵，求其中有多少个 3 × 3 幻方子矩阵
从题干易知，3 × 3 幻方必须是 1 到 9不同数字（ 第一遍解错以为大于 9 也可，审题一定要细致 😭😭😭 ）
对 3 × 3 幻方而言，其中心元素必为 5 ，因此在遍历输入矩阵时只需遍历中心元素即可，故循环条件是 [ 1 , len - 1 )
提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃
2.2 🚀 思路整理
暴力法：分别检查每 3x3 网格
对于每个网格，所有数字必不同，且在 1 到 9 之间，且每一个行，列，对角线的和必须相同 🌷🌷🌷
小细节：
① 在遍历输入矩阵时只需遍历中心元素即可
② 在判决数字必不同，且在 1 到 9 之间时，只需最值处于 [ 1 , 9 ] 即可
旋转法：三阶幻方解是固定的，有以下八种
八个解共同点，首先中间元素为五，角上元素都是偶数，中点都是奇数。同一行的解可以通过旋转得到，第一行镜像，可以得到第二行。也就是说，三阶幻方本质只有一种解，其余都是旋转镜像的体现
实现逻辑
1、依据上述，只有中心元素为五时，才判断以它是否为幻方
2、此时只需对比其余八个元素，由于解的旋转不变特性，将八个元素按顺序存放，方便后面比较，顺序如下图
3、如何旋转镜像，参考这道 189. 轮转数组 的思想，将前面部分放到后面即达到了旋转效果，镜像只需反向迭代即可
4、第二步输入的数组首位元素和 8 6 2 4 逐个比较，从目标数组中取出正向镜像两个解比较是否其一，即可确定是否为幻方 🐌🐌🐌
注：旋转法出处 ，有部分删减
整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
bool isMagic(std::vector<int>& tmpVec) { for (int targetIndex =0; targetIndex < 8; targetIndex +=2) { //遍历临时数组 if (tmpVec[0] == targetVec[targetIndex]) { //输入的数组首位元素和 8624 逐个比较 //从目标数组中取出正向镜像两个解比较是否其一 return tmpVec == std::vector<int>(targetVec.begin() + targetIndex, targetVec.begin() + targetIndex +8) || tmpVec == std::vector<int>(targetVec.rbegin() +7- targetIndex, targetVec.rbegin() +15- targetIndex); } } return false; } //初始化目标数组 std::vector<int> targetVec = { 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 }; int numMagicSquaresInside(std::vector<std::vector<int>>& grid) { //初始化矩阵 x 轴, y 轴对应偏移 std::vector<std::pair<int, int>> offsetVals = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 } }; //初始化返回值, 行列长度 int count =0, rows = grid.size() -1, columns = grid[0].size() -1; //初始化临时数组 std::vector<int> tmpVec(8); for (int i =1; i < rows; ++i) { //遍历行 for (int j =1; j < columns; ++j) { //遍历列 if (grid[i][j] ==5) { //若中心元素为 5for (int index =0; index < 8; ++index) { tmpVec[index] = grid[i + offsetVals[index].first][j + offsetVals[index].second]; //将以i,j为中心的八个元素置于 tmpVec } count += isMagic(tmpVec); //并判断其是否为幻方 } } } return count; //返回结果 }
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇
targetIndex +=2
输入的数组（tmpVec）首位元素和 8 6 2 4 逐个比较，因此索引移动两位 🐳🐳🐳
tmpVec == std::vector<int>(targetVec.begin() + i , targetVec.begin() + i +8);
旋转逻辑 ：找到目标位置后，从当前位置至当前位置移动八位（正向）
tmpVec == std::vector<int>(targetVec.rbegin() +7- i, targetVec.rbegin() +15- i);
镜像逻辑 ：找到目标位置后，从反向迭代 7 - i 至反向迭代 15 - i（反向） 🌼🌼🌼
//例如找到第一个2,对镜像而言, 它是 [ 2, 7, 6, 1, 8, 3, 4, 9 ] //即是反向迭代的 3, 4, 9, 2 这段距离 7-4=3 (targetVec.rbegin() +7- i) [ 8, 1, 6, 7, 2, 9, 4, 3, 8, 1, 6, 7, 2, 9, 4, 3 ]
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理没有问题
代码实现时使用了暴力解（官网题解同暴力，旋转法确实难想），简洁性差 😭😭😭 ，代码如下 👇👇👇👇
int numMagicSquaresInside(vector<vector<int>>& grid) { int count =0; int width = grid.size(), high = grid[0].size(); for (int i =1; i < width -1; ++i) { //遍历二维输入的宽 for (int j =1; j < high -1; ++j) { if (grid[i][j] !=5) continue; if (grid[i-1][j] == grid[i][j]) continue; //各个数值不相同 //横向加和 if (grid[i-1][j-1] + grid[i][j-1] + grid[i+1][j-1] !=15) continue; if (grid[i-1][j] + grid[i][j] + grid[i +1][j] !=15) continue; if (grid[i-1][j+1] + grid[i][j+1] + grid[i+1][j+1] !=15) continue; //竖向加和 if (grid[i-1][j-1] + grid[i-1][j] + grid[i-1][j+1] !=15) continue; if (grid[i][j-1] + grid[i][j] + grid[i][j+1] !=15) continue; if (grid[i+1][j-1] + grid[i+1][j] + grid[i+1][j+1] !=15) continue; //对角加和 if (grid[i-1][j-1] + grid[i][j] + grid[i+1][j+1] !=15) continue; if (grid[i-1][j+1] + grid[i][j] + grid[i+1][j-1] !=15) continue; //求最大值和最小值 legalScope int mem_max = std::max({grid[i-1][j-1], grid[i][j-1], grid[i+1][j-1], grid[i-1][j], grid[i][j], grid[i+1][j], grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]}); int mem_min = std::min({grid[i-1][j-1], grid[i][j-1], grid[i+1][j-1], grid[i-1][j], grid[i][j], grid[i+1][j], grid[i-1][j+1], grid[i][j+1], grid[i+1][j+1]}); if (mem_max <=9 && mem_min >=1) ++count; } } return count; }
