# 840. 矩阵中的幻方

力扣原题链接(点我直达) (opens new window)

3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的 grid,其中有多少个 3 × 3 的 “幻方” 子矩阵?(每个子矩阵都是连续的)。

示例:

输入: [[4,3,8,4],
      [9,5,1,9],
      [2,7,6,2]]
输出: 1
解释: 
下面的子矩阵是一个 3 x 3 的幻方:
438
951
276

而这一个不是:
384
519
762

总的来说,在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提示:

  1. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. 0 <= grid[i][j] <= 15

# 第一版,没意思,纯暴力法,就是比较麻烦

执行用时 :8 ms, 在所有 cpp 提交中击败了51.79%的用户

内存消耗 :9.4 MB, 在所有 cpp 提交中击败了19.05%的用户

int equal(vector<int>& a, vector<int>& b, vector<int>& c) {
	
	//cout << a[0] << a[1] << a[2] << endl;
	//cout << b[0] << b[1] << b[2] << endl;
	//cout << c[0] << c[1] << c[2] << endl;

	unordered_set<int> res;
	for (auto& i : a) {
		if (i < 1 || i > 9) return 0;
		res.insert(i);
	}
	if (res.size() != 3) return 0;
	for (auto& i : b) {
		if (i < 1 || i > 9) return 0;
		res.insert(i);
	}
	if (res.size() != 6) return 0;
	for (auto& i : c) {
		if (i < 1 || i > 9) return 0;
		res.insert(i);
	}
	if (res.size() != 9) return 0;


	
	int sum = a[0] + a[1] + a[2];
	if (sum == b[0] + b[1] + b[2] && c[0] + c[1] + c[2] == sum) {//行
		if (a[0] + b[0] + c[0] == sum && a[1] + b[1] + c[1]== sum &&  a[2] + b[2] + c[2]==sum) {//列			
			if (a[0] + b[1]+c[2] ==sum&&b[1]+ a[2] + c[0] ==sum) //a0+b1+c2   a2+b1+c0
				return 1;
			else
				return 0;		
		}
		else
			return 0;
	}
	else
		return 0;
}


int numMagicSquaresInside(vector<vector<int>>& grid) {
	if (grid.size() < 3 || grid[0].size() < 3) return 0;
	int count = 0;
	vector<int> a, b, c;
	a.resize(3);
	b.resize(3);
	c.resize(3);
	int len1 = grid.size(), len2 = grid[0].size();//len1=3,len2=4
	for (int i = 0; i <= len1 - 3; ++i) {
		int j = 0;
		while (j <= len2 - 3) {


			a[0]=(grid[i][j + 0]);
			a[1] = (grid[i][j + 1]);
			a[2] = (grid[i][j + 2]);
			//cout << j << " ";
			b[0] = (grid[i+1][j + 0]);
			b[1] = (grid[i+1][j + 1]);
			b[2] = (grid[i+1][j + 2]);
			//cout << j << " ";
			c[0] = (grid[i + 2][j + 0]);
			c[1] = (grid[i + 2][j + 1]);
			c[2] = (grid[i + 2][j + 2]);
			//cout << j << " " << endl;
			count += equal(a, b, c);
			j++;
			//cout << j << " ";
			//cout << endl << "count " << count<<endl;

		}
		//cout << endl;
	}

	return count;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

# 第二版,经过提示,改进一点

执行用时 :8 ms, 在所有 cpp 提交中击败了51.79%的用户

内存消耗 :8.9 MB, 在所有 cpp 提交中击败了78.57%的用户

中心点必须是5,且每行每列都需要是15才可以

int equal(vector<int>& a, vector<int>& b, vector<int>& c) {
	
	//cout << a[0] << a[1] << a[2] << endl;
	//cout << b[0] << b[1] << b[2] << endl;
	//cout << c[0] << c[1] << c[2] << endl;

	unordered_set<int> res;
	for (auto& i : a) {
		if (i < 1 || i > 9) return 0;
		res.insert(i);
	}
	if (res.size() != 3) return 0;
	for (auto& i : b) {
		if (i < 1 || i > 9) return 0;
		res.insert(i);
	}
	if (res.size() != 6) return 0;
	for (auto& i : c) {
		if (i < 1 || i > 9) return 0;
		res.insert(i);
	}
	if (res.size() != 9) return 0;


	
	int sum = a[0] + a[1] + a[2]; //sum其实必须是15才可以
	if (sum == b[0] + b[1] + b[2] && c[0] + c[1] + c[2] == sum) {//行
		if (a[0] + b[0] + c[0] == sum && a[1] + b[1] + c[1]== sum &&  a[2] + b[2] + c[2]==sum) {//列			
			if (a[0] + b[1]+c[2] ==sum&&b[1]+ a[2] + c[0] ==sum) //a0+b1+c2   a2+b1+c0
				return 1;
			else
				return 0;		
		}
		else
			return 0;
	}
	else
		return 0;
}


int numMagicSquaresInside(vector<vector<int>>& grid) {
	if (grid.size() < 3 || grid[0].size() < 3) return 0;
	int count = 0;
	vector<int> a, b, c;
	a.resize(3);
	b.resize(3);
	c.resize(3);
	int len1 = grid.size(), len2 = grid[0].size();//len1=3,len2=4
	for (int i = 0; i <= len1 - 3; ++i) {
		int j = 0;
		while (j <= len2 - 3) {

			if (grid[i + 1][j + 1] != 5) { 
				j++;
				continue; 
			}

			a[0]=(grid[i][j + 0]);
			a[1] = (grid[i][j + 1]);
			a[2] = (grid[i][j + 2]);
			//cout << j << " ";
			b[0] = (grid[i+1][j + 0]);
			b[1] = (grid[i+1][j + 1]);
			b[2] = (grid[i+1][j + 2]);
			//cout << j << " ";
			c[0] = (grid[i + 2][j + 0]);
			c[1] = (grid[i + 2][j + 1]);
			c[2] = (grid[i + 2][j + 2]);
			//cout << j << " " << endl;
			count += equal(a, b, c);
			j++;
			//cout << j << " ";
			//cout << endl << "count " << count<<endl;

		}
		//cout << endl;
	}

	return count;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82