洛谷 P2370 魔板 magic squares 题解

每日一题 day67 打卡

Analysis

这道题很容易想到广搜，但是有一个难题需要我们解决，就是如何储存魔板最方便操作。

我选择的方法是直接将魔板变成一个8位数，

注意：

如果魔板是这样

1 2 3 4

5 6 7 8

存起来就是12345678，而不是顺时针的顺序。

那么既然这个问题解决了，每次ABC的操作都可以用一个简单的打表完成。

最后我们需要在结构体中多加一个father（每次广搜时即为head的值）来用于回溯路径（也就是用于最后输出操作序列）

这次用的是手写队列，一个原因是是复习一下怎么写，另外时间也比STL中的queue快

  1 #include
  2 #include
  3 #include
  4 #include
  5 #define int long long
  6 #define maxn 9000005
  7 #define maxm 100005
  8 #define rep(i,s,e) for(register int i=s;i<=e;++i)
  9 #define dwn(i,s,e) for(register int i=s;i>=e;--i)
 10 using namespace std;
 11 inline int read()
 12 {
 13     int x=0,f=1;
 14     char c=getchar();
 15     while(c<'0'||c>'9') {if(c=='-') x=-x; c=getchar();}
 16     while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
 17     return f*x;
 18 }
 19 inline void write(int x)
 20 {
 21     if(x<0){putchar('-');x=-x;}
 22     if(x>9)write(x/10);
 23     putchar(x%10+'0');
 24 }
 25 int ans[9],bit[9],cnt;
 26 bool book[maxn],flag;
 27 struct node
 28 {
 29     int con[9],fa;
 30     char step;
 31 }x[maxm];
 32 inline int hash(int a[])
 33 {
 34     int res=0;
 35     dwn(i,7,1) res=res*10+a[i];
 36     return res;
 37 }
 38 void output(int a)
 39 {
 40     if(x[a].fa!=0)
 41     {
 42         ++cnt;
 43         output(x[a].fa);
 44     }
 45     if(x[a].fa==0) return;
 46     if(flag==0)
 47     {
 48         write(cnt);
 49         putchar('\n');
 50         flag=1;
 51     }
 52     printf("%c",x[a].step);
 53 }
 54 void bfs()
 55 {
 56     int head=0,tail=1;
 57     x[tail].fa=0;
 58     while(head<tail)
 59     {
 60         ++head;
 61         rep(i,1,3)
 62         {
 63             if(i==1)
 64             {
 65                 for(int i=1;i<=4;i++)
 66                 {
 67                     bit[i]=x[head].con[i+4];
 68                     bit[i+4]=x[head].con[i];
 69                 }    
 70             }
 71             if(i==2)
 72             {
 73                 bit[1]=x[head].con[4];bit[5]=x[head].con[8];
 74                 bit[2]=x[head].con[1];bit[6]=x[head].con[5];
 75                 bit[3]=x[head].con[2];bit[7]=x[head].con[6];
 76                 bit[4]=x[head].con[3];bit[8]=x[head].con[7];
 77             }
 78             if(i==3)
 79             {
 80                 bit[1]=x[head].con[1];
 81                 bit[2]=x[head].con[6];
 82                 bit[3]=x[head].con[2];
 83                 bit[4]=x[head].con[4];
 84                 bit[5]=x[head].con[5];
 85                 bit[8]=x[head].con[8];
 86                 bit[7]=x[head].con[3];
 87                 bit[6]=x[head].con[7];
 88             }
 89             if(book[hash(bit)]==0)
 90             {
 91                 ++tail;
 92                 if(i==1) x[tail].step='A';
 93                 if(i==2) x[tail].step='B';
 94                 if(i==3) x[tail].step='C';
 95                 book[hash(bit)]=1;
 96                 x[tail].fa=head;
 97                 rep(i,1,8) x[tail].con[i]=bit[i];
 98                 if(hash(bit)==hash(ans))
 99                 {
100                     output(tail);
101                     exit(0);
102                 }
103             }
104         }
105         
106     }
107 }
108 signed main()
109 {
110     rep(i,1,8)
111     {
112         if(i<=4) x[1].con[i]=i;
113         if(i>4) x[1].con[i]=13-i;
114     }
115     book[hash(x[1].con)]=1;
116     rep(i,1,4) ans[i]=read();
117     dwn(i,8,5) ans[i]=read();
118     if(hash(x[1].con)==hash(ans)) 
119     {
120         write(0);
121         return 0;
122     }
123     bfs();
124     return 0;
125 }

如有失误请各位大佬斧正（反正我不认识斧正是什么意思）