蓝桥杯2017年第八届真题-九宫幻方(搜索)

解题思路:
单纯的九宫格情况只有9!=362880种，而且这个是带有限制的九宫格，情况更少，处理好重复情况搜索就行。
注意事项:
先处理出题目所示的所有情况，然后枚举目标的所有可能，看是否在题目的要求内。

旋转有顺逆时针，翻转有上下左右，共四种
参考代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<string,int> M;
int all[5][5];
int all1[5][5];
int MM[20];
string s;
vector<char> ss;
int ans=0;
void dfs()
{
  s.clear();
   for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
     s+=(all[i][j]+'0');
     if(M.count(s)==1) return ;
     else M[s]=1;
     //cout<<s<<"\n";

    int all2[5][5];
    for(int i=1;i<=3;++i)
     for(int j=1;j<=3;++j)
      all2[i][j]=all[i][j];
   //顺时针旋转
   all1[1][2]=all[1][1];all1[1][3]=all[1][2];
   all1[2][3]=all[1][3];all1[3][3]=all[2][3];
   all1[3][2]=all[3][3];all1[3][1]=all[3][2];
   all1[2][1]=all[3][1];all1[1][1]=all[2][1];
   all1[2][2]=all[2][2];
   for(int i=1;i<=3;++i)
     for(int j=1;j<=3;++j)
      all[i][j]=all1[i][j];
      dfs();
  //逆时针
     for(int i=1;i<=3;++i)
     for(int j=1;j<=3;++j)
      all[i][j]=all2[i][j];
         
   all1[1][2]=all[1][3];all1[1][3]=all[2][3];
   all1[2][3]=all[3][3];all1[3][3]=all[3][2];
   all1[3][2]=all[3][1];all1[3][1]=all[2][1];
   all1[2][1]=all[1][1];all1[1][1]=all[1][2];
   all1[2][2]=all[2][2];
   for(int i=1;i<=3;++i)
     for(int j=1;j<=3;++j)
      all[i][j]=all1[i][j];
      dfs();
   //上下翻转
   for(int i=1;i<=3;++i)
     for(int j=1;j<=3;++j)
      all[i][j]=all2[i][j];
   for(int i=1;i<=3;++i)
   swap(all[1][i],all[3][i]);
   dfs();
   //左右
   for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
    all[i][j]=all2[i][j];
   for(int i=1;i<=3;++i)
   swap(all[i][1],all[i][1]);
   dfs();
   //结束
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
    all[i][j]=all2[i][j];
}
void dfs2(int i,int j)
{
   if(i==4)
   {
    s.clear();
    for(int i=1;i<=3;++i)
     for(int j=1;j<=3;++j)
      s+=(all[i][j]+'0');
      //cout<<s;
      if(M.count(s)==1) ++ans;
      if(ans==1)
      {
        for(int i=0;i<9;++i)
         ss.push_back(s[i]);
      }
    return ;
   }
   if(all[i][j]!=0)
   {
        if(j==3) dfs2(i+1,1);
        else    dfs2(i,j+1);
        return ;
   }
  for(int k=1;k<=9;++k)
   {
    if(MM[k]!=0) continue;
    all[i][j]=k;
    MM[k]=1;
    if(j==3) dfs2(i+1,1);
    else    dfs2(i,j+1);
    all[i][j]=0;
    MM[k]=0;
   }
}
 

signed main()
{
 all[1][1]=4;all[1][2]=9;all[1][3]=2;
 all[2][1]=3;all[2][2]=5;all[2][3]=7;
 all[3][1]=8;all[3][2]=1;all[3][3]=6;
 dfs();
 for(int i=1;i<=3;++i)
  for(int j=1;j<=3;++j)
   all[i][j]=0;
 for(int i=1;i<=3;++i)
  for(int j=1;j<=3;++j)
   {cin>>all[i][j];
    MM[all[i][j]]=1;}
   
   dfs2(1,1);
   int neww=-1;
  if(ans==1)
   {
    for(int i=1;i<=3;++i)
   {
   for(int j=1;j<3;++j)
   cout<<ss[++neww]<<" ";
   cout<<ss[++neww]<<"\n";
   }

   }
  else
  cout<<"Too Many";
}