我搜了一下康拓展開定理結果下面解釋就是用這題的做例子。稍微改一下就行了。vis不僅記錄了他是否被便利過了還可以順便用來計數不過注意當m==0是vis[0]==0但是contor數為0的數列就是12345678是訪問過的。去掉就行了。還有這一題當改變次數為0時要輸出兩個換行不知道為什么。

/*
ID: jinbo wu
TASK: msquare
LANG:C++
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=40321;
const int fac[8] = { 1, 1, 2, 6, 24, 120, 720, 5040 };
string ans[maxn];
int  vis[maxn];
struct node
{int a[8];
}b;
int contor(node&t)
{int num=0,tmp;for(int i=0;i<8;i++){tmp=0;for(int j=i+1;j<8;j++){if(t.a[i]>t.a[j])tmp++;}num+=tmp*fac[7-i];}return num;
}
void A(node&t)
{swap(t.a[0],t.a[7]);swap(t.a[1],t.a[6]);swap(t.a[2],t.a[5]);swap(t.a[3],t.a[4]);
}
void B(node&t)
{swap(t.a[3],t.a[2]);swap(t.a[4],t.a[5]);swap(t.a[2],t.a[1]);swap(t.a[5],t.a[6]);swap(t.a[1],t.a[0]);swap(t.a[6],t.a[7]);
}
void C(node&t)
{swap(t.a[6],t.a[2]);swap(t.a[1],t.a[2]);swap(t.a[6],t.a[5]);
}
void init()
{node t;for(int i=0;i<8;i++)t.a[i]=i+1;queue<node> q;q.push(t);vis[0]=0;while(!q.empty()){t=q.front();q.pop();for(int i=0;i<3;i++){node v=t;switch (i){case 0 :{A(v);break;}case 1 : {B(v);break;}case 2 :{C(v);break;} }int m=contor(v);if(!vis[m]&&m!=0){vis[m]=vis[contor(t)]+1;;q.push(v);char ch='A'+i;ans[m]=ans[contor(t)]+ch;}}}
}
int main()
{freopen("msquare.in","r",stdin);freopen("msquare.out","w",stdout);init();for(int i=0;i<8;i++)cin>>b.a[i];int k=contor(b);cout<<vis[k]<<endl;if(vis[k]==0)cout<<endl;int l=0;while(ans[k][l]!='\0'){for(int i=0;i<=60&&ans[k][l]!='\0';i++)cout<<ans[k][l++];cout<<endl;}
//	cout<<endl;
}

總結

以上是生活随笔為你收集整理的usaco Magic Squares的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。