hiho 第135周 九宫

题目链接:http://hihocoder.com/contest/hiho135/problem/1

由于是九宫格,全排列也就是9! (362880)种方式,我就直接暴力枚举排列好了。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 int a[3][3];
  6 int b[3][3];
  7 bool vis[10];
  8 int num[10];
  9 int cnt;
 10 
 11 bool check() {
 12     int num = b[0][0] + b[0][1] + b[0][2];
 13     int num2 = 0;
 14     for(int i=0;i<3;i++)
 15         num2 +=b[1][i];
 16     if(num2!=num) return false;
 17 
 18     num2 = 0;
 19     for(int i=0;i<3;i++)
 20         num2+=b[2][i];
 21     if(num2!=num) return false;
 22 
 23     for(int i=0;i<3;i++)
 24     {
 25         num2 = 0;
 26         for(int j=0;j<3;j++)
 27         {
 28             num2 +=b[j][i];
 29         }
 30         if(num2!=num)
 31             return false;
 32     }
 33 
 34     num2 = 0;
 35     for(int i=0;i<3;i++)
 36         num2 +=b[i][i];
 37     if(num2!=num)
 38         return false;
 39 
 40     num2 = 0;
 41     for(int i=0;i<3;i++)
 42         num2 +=b[i][2-i];
 43     if(num2!=num)
 44         return false;
 45 
 46     return true;
 47 }
 48 
 49 int main()
 50 {
 51     cnt = 0;
 52     for(int i=0;i<3;i++)
 53         for(int j=0;j<3;j++) {
 54             scanf("%d",&a[i][j]);
 55             if(a[i][j])
 56                 vis[a[i][j]] = true;
 57         }
 58 
 59 
 60     for(int i=1;i<=9;i++)
 61         if(!vis[i]) {
 62             num[cnt++] = i;
 63         }
 64 
 65     vector <int> ans[10000];
 66     int ansnum = 0;
 67 
 68     do {
 69         int k = 0;
 70         for(int i=0;i<3;i++) {
 71             for(int j=0;j<3;j++) {
 72                 if(a[i][j]==0)
 73                     b[i][j]=num[k++];
 74                 else b[i][j] = a[i][j];
 75             }
 76         }
 77 
 78         if(check())
 79         {
 80             for(int i=0;i<3;i++)
 81                 for(int j=0;j<3;j++)
 82                     ans[ansnum].push_back(b[i][j]);
 83             ansnum++;
 84         }
 85 
 86     }while(next_permutation(num,num+cnt));
 87 
 88     if(ansnum>1)
 89         puts("Too Many");
 90     else if(ansnum==1)
 91     {
 92         int k = 0;
 93         for(int i=0;i<3;i++)
 94         {
 95             for(int j=0;j<3;j++)
 96             {
 97                 printf("%d ",ans[0][k++]);
 98             }
 99             puts("");
100         }
101     }
102     return 0;
103 }
原文地址:https://www.cnblogs.com/TreeDream/p/6357962.html