時(shí)間限制:10000ms 單點(diǎn)時(shí)限:1000ms 內(nèi)存限制:256MB
小Hi最近在教鄰居家的小朋友小學(xué)奧數(shù)，而最近正好講述到了三階幻方這個(gè)部分，三階幻方指的是將1~9不重復(fù)的填入一個(gè)3*3的矩陣當(dāng)中，使得每一行、每一列和每一條對(duì)角線的和都是相同的。
三階幻方又被稱作九宮格，在小學(xué)奧數(shù)里有一句非常有名的口訣：“二四為肩，六八為足，左三右七，戴九履一，五居其中”，通過這樣的一句口訣就能夠非常完美的構(gòu)造出一個(gè)九宮格來。
有意思的是，所有的三階幻方，都可以通過這樣一個(gè)九宮格進(jìn)行若干鏡像和旋轉(zhuǎn)操作之后得到。現(xiàn)在小Hi準(zhǔn)備將一個(gè)三階幻方（不一定是上圖中的那個(gè)）中的一些數(shù)組抹掉，交給鄰居家的小朋友來進(jìn)行還原，并且希望她能夠判斷出究竟是不是只有一組解。
而你呢，也被小Hi交付了同樣的任務(wù)，但是不同的是，你需要寫一個(gè)程序~
輸入僅包含單組測(cè)試數(shù)據(jù)。
每組測(cè)試數(shù)據(jù)為一個(gè)3*3的矩陣，其中為0的部分表示被小Hi抹去的部分。
對(duì)于100%的數(shù)據(jù)，滿足給出的矩陣至少能還原出一組可行的三階幻方。
如果僅能還原出一組可行的三階幻方，則將其輸出，否則輸出“Too Many”（不包含引號(hào)）。
0 7 2 0 5 0 0 3 0
6 7 2 1 5 9 8 3 4
這道題本來還有更簡單的辦法解決，網(wǎng)上搜了題解，直接打表可過。為了練習(xí)一下dfs（可參考前一篇博客），所以還是用深搜寫的：
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=10;int a[maxn],anss[maxn];int visit[maxn+1];int ans;bool check(int *a){ int i; for (i=0; i<3; i++) if ((a[i*3+0]+a[i*3+1]+a[i*3+2])!=15) return false; for (i=0; i<3; i++) if ((a[i+0]+a[i+3]+a[i+6])!=15) return false; if ((a[0]+a[4]+a[8]!=15) || (a[2]+a[4]+a[6])!=15) return false; return true; }bool dfs(int pos){ if (pos>=9 && check(a)) { ans++; memcpy(anss,a,sizeof(a)); return true; } if (a[pos]) dfs(pos+1); else { for (int i=1; i<=9; i++) { if (!visit[i]) { visit[i]=1; a[pos]=i; dfs(pos+1); visit[i]=0; a[pos]=0; } } } return false;}int main(){ int i=0; for (i=0; i<9; i++) { scanf("%d",&a[i]); visit[a[i]]=1; } dfs(0); if (ans==1) { for (i=0; i<9; i++) {新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
