数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中统计幻方个数
给定一个数字矩阵，目标是找到该矩阵中存在的幻方数量。
幻方，如果作为一个矩阵，是一个3x3的矩阵，其中包含从1到9的元素，就像数独中的网格一样。属性如下：
- 所有数字都恰好出现一次。
- 矩阵中所有9个单元格的总和为45。
- 每行3个数字的和为15。
- 每列3个数字的和为15。
- 对角线3个数字的和为15。
- 为了得到这样的和，5总是位于两个对角线的中间。
输入
int arr[][]= { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };输出
Magic Squares present: 0
说明 − 建立矩阵形式以便理解 −
| 1 | 2 | 3 | 0 |
| 4 | 5 | 6 | 1 |
| 7 | 8 | 9 | 0 |
所有元素都在1到9之间且唯一。但是，
1+2+3=6 != 4+5+6=15 != 7+8+9=23
对角线之和也不等于15。
输入
arr[][]= { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };输出
Magic Squares present : 1
说明 − 建立矩阵形式以便理解 −
| 1 | 6 | 8 | 4 |
| 8 | 1 | 6 | 0 |
| 3 | 5 | 7 | 1 |
| 4 | 9 | 2 | 0 |
所有数字都是唯一的，并且在1到9的范围内。
行和，8+1+6=3+5+7=4+9+2=15
列和，8+3+4=1+5+9=6+7+2=15
对角线和，8+5+2=4+5+6=15
此外，将1到9相加得到45，而5位于两个对角线的中间。
下面程序中使用的算法如下
整数数组Grid[][]存储数字，row和col存储其维度。
函数magicSquare(int a, int b……int i) 将所有9个元素作为输入，并检查它是否构成幻方。如果是幻方，则返回1；否则返回0。
在这里，我们将使用数组arr[9]来存储所有参数，并通过检查它们是否占据数组中的唯一单元格来检查它们是否唯一。如果一个单元格的计数count<1，则表示该数字不在1到9的范围内，或者如果count>1，则表示该数字不唯一。将flag设置为0。
如果flag为1，我们将检查行、列、对角线之和是否为15。如果为真，则它是一个幻方。返回1，否则返回0。
函数countSquares(int G[3][4],int R, int C) 将网格、其行和列作为输入，并计算其中存在的幻方数量。
Count用于存储此类正方形的数量。
从第一个元素开始遍历到row-2, col-2 (3x3矩阵)
如果对角线的中间元素G[i+1][j+1]不是5，则不可能形成幻方，跳过当前迭代。
否则，通过将其传递给magicSquare(int a到i)来检查所有9个元素。
所有9个元素包括G[i][j]、G[i+1][j]、G[i+2][j]、G[i+1][j+1]、G[i][j+1]、G[i][j+2]、G[i+2][j+2]、G[i+2][j+1]、G[i+1][j+2]
如果返回1，则计数加1。
最后返回计数作为期望的结果。
示例
#include <bits/stdc++.h>
using namespace std;
// to check is subgrid is Magic Square
int magicSquare(int a, int b, int c, int d, int e,
int f, int g, int h, int i){
int flag=1; // to mark all numbers are unique and between 1 to 9
int arr[9]={0};
arr[a-1]++;
arr[b-1]++;
arr[c-1]++;
arr[d-1]++;
arr[e-1]++;
arr[f-1]++;
arr[g-1]++;
arr[h-1]++;
arr[i-1]++;
for(int i=0;i<9;i++)
if(arr[i]>1 || arr[i]<1) //every number occurs exactly once{
flag=0;
break;
}
// checking all sums as 15
if (flag==1 && (a + b + c) == 15 && (d + e + f) == 15 && (g + h + i) == 15 && (a + d + g) == 15 &&(b + e + h) == 15 && (c + f + i) == 15 &&(a + e + i) == 15 && (c + e + g) == 15)
return 1;
return 0;
}
int countSquares(int G[3][4],int R, int C){
int count = 0;
for (int i = 0; i < R - 2; i++)
for (int j = 0; j < C - 2; j++) {
if (G[i + 1][j + 1] != 5)
continue;
int ismagic=magicSquare(G[i][j], G[i][j + 1], G[i][j + 2], G[i + 1][j], G[i + 1][j + 1],
G[i + 1][j + 2], G[i + 2][j], G[i + 2][j + 1], G[i + 2][j + 2]);
// check for magic square subgrid
if (ismagic==1)
count++;
}
return count;
}
int main(){
int Grid[3][4] = { { 4, 3, 8, 4 },{ 9, 5, 1, 9 },{ 2, 7, 6, 2 } };
int row=3;
int col=4;
cout <<"Count of Magic Squares in Grid: "<<countSquares(Grid,row,col);
return 0;
}输出
Count of Magic Squares in Grid: 1
242 次查看
