題目描述 小明最近在教鄰居家的小朋友國小奧數,而最近正好講述到了三階幻方這個部分,三階幻方指的是将1~9不重複的填入一個3*3的矩陣當中,使得每一行、每一列和每一條對角線的和都是相同的。
三階幻方又被稱作九宮格,在國小奧數裡有一句非常有名的口訣:“二四為肩,六八為足,左三右七,戴九履一,五居其中”,通過這樣的一句口訣就能夠非常完美的構造出一個九宮格來。
4 9 2
3 5 7
8 1 6
有意思的是,所有的三階幻方,都可以通過這樣一個九宮格進行若幹鏡像和旋轉操作之後得到。現在小明準備将一個三階幻方(不一定是上圖中的那個)中的一些數抹掉,交給鄰居家的小朋友來進行還原,并且希望她能夠判斷出究竟是不是隻有一個解。
而你呢,也被小明傳遞了同樣的任務,但是不同的是,你需要寫一個程式~ 輸入 輸入僅包含單組測試資料。
每組測試資料為一個3*3的矩陣,其中為0的部分表示被小明抹去的部分。
對于100%的資料,滿足給出的矩陣至少能還原出一組可行的三階幻方。 輸出 如果僅能還原出一組可行的三階幻方,則将其輸出,否則輸出“Too Many”(不包含引号)。 樣例輸入
0 7 2
0 5 0
0 3 0
樣例輸出
6 7 2
1 5 9
8 3 4
提示 笨笨有話說:
我最喜歡這類題目了。既然九宮幻方一共也沒有多少,我就不辭辛勞地一個一個寫出來好了。
也不能太過分,好歹用個數組。 思路:把這九個數字當做一維數組b[9]輸入,然後對數字1-9進行枚舉全排列a[9], 當b[i]不為0的情況下,a[i]與b[i]對應相等時, 并且數組a滿足九宮幻方的特點時,計數次數cnt +1,并把a[]儲存到結果數組result[]中。 注意:由于此處隻用到了數組中的部分數字,是以需要考慮對局面進行判重,但是考慮到本題的實際情況,是以并不需要判重。
1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4
5 using namespace std;
6
7 int a[9] = {1,2,3,4,5,6,7,8,9}; // 進行枚舉的全排列數組
8 int b[9]; // 一開始輸入的3×3數組
9 int result[9]; // 儲存結果的數組
10
11 int main()
12 {
13 for(int i = 0; i < 9; ++i)
14 cin >> b[i];
15
16 int cnt = 0;
17 do
18 {
19 int flag = 1;
20 for(int i = 0; i < 9; ++i)
21 {
22 if(b[i] != 0)
23 {
24 if(a[i] != b[i])
25 {
26 flag = 0;
27 break;
28 }
29 }
30 }
31
32 if(flag == 0)
33 continue;
34 else
35 {
36 int sum1 = a[0] + a[1] + a[2];
37 int sum2 = a[0] + a[3] + a[6];
38 int sum3 = a[6] + a[7] + a[8];
39 int sum4 = a[2] + a[5] + a[8];
40 int sum5 = a[0] + a[4] + a[8];
41 int sum6 = a[2] + a[4] + a[6];
42 if(sum1 == sum2 && sum2 == sum3 && sum3 == sum4 && sum4 == sum5 && sum5 == sum6)
43 {
44 memcpy(result, a,sizeof(a));
45 cnt++;
46 }
47 }
48
49 }while(next_permutation(a,a+9));
50
51 if(cnt == 1)
52 {
53 for(int i = 0; i < 9; ++i)
54 {
55 if(i % 3 == 2)
56 cout << result[i] << endl;
57 else
58 cout << result[i] << ' ';
59 }
60 }
61 else
62 cout << "Too Many" << endl;
63
64 return 0;
65 }
轉載于:https://www.cnblogs.com/FengZeng666/p/10576303.html