P1092 蟲食算

---

題目正解是\(O(2^NN^3)\)的高斯消元加上二進(jìn)制枚舉

然而這并不妨礙我們搜索的腳步。（滑稽

我們可以考慮按照位置從左往右進(jìn)行搜索，每列最多搜索兩個(gè)數(shù)，在利用之間的關(guān)系計(jì)算出來剩下的一個(gè)數(shù)。可以根據(jù)這個(gè)剪枝

然后就可以考慮寫代碼了

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> const int N=28; int M[N][3],n; int D[N],V[N];//D為進(jìn)位，V為第i個(gè)字母的數(shù)值 bool G[N],Num[N];//G為第i個(gè)字母是否被填充過，Num為某個(gè)數(shù)字是否被使用過 int read_char() {char c=getchar();while(c>'Z'||c<'A') c=getchar();return c-'A'+1; } bool fill(int pos,int val) {if(!G[pos]&&!Num[val]){G[pos]=true;V[pos]=val;Num[val]=true;return true;}if(V[pos]==val) return true;return false; } inline int calc(int now) {return V[M[now][1]]+V[M[now][2]]+D[now]; } inline void reset(int pos) {G[pos]=false;Num[V[pos]]=false;V[pos]=-1; } void Exit() {/*for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d",V[j]);printf("\n");}*/for(int i=1;i<=n;i++)printf("%d ",V[i]);exit(0); } void dfs(int now) {if(now==n+1)//終止條件{if(!D[now])//D數(shù)組的意思是，now列有沒有進(jìn)位Exit();return ;}bool N1=G[M[now][1]],N2=G[M[now][2]],N3=G[M[now][3]];//Ni表示從上往下數(shù)第i個(gè)數(shù)有沒有被使用if(!(N1&&N3&&!N2))//如果不是第一個(gè)數(shù)和第三個(gè)數(shù)有值，第二個(gè)數(shù)沒有數(shù)值的情況{for(int i=n-1;i>=0;i--){if(!N1&&!fill(M[now][1],i)) continue;//如果第一個(gè)數(shù)沒有數(shù)值，則嘗試填入。能否成功由fill函數(shù)返回，如果能填進(jìn)去i或者是第一個(gè)數(shù)的值是i，返回true//如果N1為true，不進(jìn)行上面的操作for(int j=n-1;j>=0;j--){if(!N2&&!fill(M[now][2],j)) continue;//同理int C=calc(now);//計(jì)算出第三個(gè)數(shù)if(fill(M[now][3],C%n))//判斷填入是否合法{D[now+1]=C/n;//計(jì)算進(jìn)位dfs(now+1);//下一層遞歸D[now+1]=0;//進(jìn)位重置if(!N3) reset(M[now][3]);//復(fù)位}if(N2) break;//如果N2為true，則這個(gè)循環(huán)只執(zhí)行一次reset(M[now][2]);//重置}if(N1) break;reset(M[now][1]);//同上}}else{int B=(V[M[now][3]]+n-V[M[now][1]]-D[now])%n;//計(jì)算出中間的數(shù)值來if(fill(M[now][2],B)){D[now+1]=(V[M[now][1]]+D[now]+B)/n;dfs(now+1);D[now+1]=0;reset(M[now][2]);}}//其實(shí)還可以更快，即是根據(jù)后兩個(gè)數(shù)值，計(jì)算出第一個(gè)數(shù)來 } int main() {scanf("%d",&n);for(int i=1;i<=3;i++)for(int j=n;j>=1;j--)M[j][i]=read_char();//讀入數(shù)據(jù)for(int i=1;i<=n;i++) reset(i);dfs(1); }

轉(zhuǎn)載于:https://www.cnblogs.com/Lance1ot/p/9781560.html

總結(jié)

以上是生活随笔為你收集整理的虫食算（暴力搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。