【BZOJ1814】Ural 1519 Formula 1

題意：一個 m * n 的棋盤,有的格子存在障礙,求經(jīng)過所有非障礙格子的哈密頓回路個數(shù)。(n,m<=12)

題解：插頭DP板子題，刷板子，附帶題解鏈接。

如何存放狀態(tài)呢？可以采用hash，我們的hash表形如一個隊(duì)列，每次新加入一個狀態(tài)時，就沿著這個狀態(tài)在隊(duì)列中對應(yīng)的hash值不斷向后找，直到找到這個狀態(tài)或者發(fā)現(xiàn)一個空位為止。

本題我的狀態(tài)采用了4進(jìn)制表示。

?

#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; const int limit=99991; int n,m,k,tot[2],nn,mm; bool v[20][20]; char str[20]; ll tag,ans; int hs[limit],state[2][limit]; ll dp[2][limit]; inline void upd(ll S) {register int pos=S%limit;while(hs[pos]){if(state[k][hs[pos]]==S){dp[k][hs[pos]]+=tag;return ;}pos++;if(pos==limit) pos=0;}hs[pos]=++tot[k],state[k][tot[k]]=S,dp[k][tot[k]]=tag; } int main() {register int i,j,t,u,tmp,p,q,x,y,S,T;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%s",str+1);for(j=1;j<=m;j++)asdasd{v[i][j]=str[j]=='.';if(v[i][j]) nn=i,mm=j;}}tot[0]=1,state[0][1]=0,dp[0][1]=1;for(i=1;i<=n;i++){for(j=1;j<=m;j++){k^=1;memset(hs,0,sizeof(hs));memset(state[k],0,sizeof(state[k][0])*(tot[k]+1));memset(dp[k],0,sizeof(dp[k][0])*(tot[k]+1));tot[k]=0;for(t=1;t<=tot[k^1];t++){S=state[k^1][t],tag=dp[k^1][t],y=j<<1,x=y-2,p=(S>>x)&3,q=(S>>y)&3,T=S^(p<<x)^(q<<y);if(!v[i][j]){if(!p&&!q) upd(T);continue;}if(p==0&&q==0&&v[i][j+1]&&v[i+1][j]){upd(T|(1<<x)|(2<<y));continue;}if((p==0&&q==1)||(p==1&&q==0)){if(v[i+1][j]) upd(T|(1<<x));if(v[i][j+1]) upd(T|(1<<y));continue;}if((p==0&&q==2)||(p==2&&q==0)){if(v[i+1][j]) upd(T|(2<<x));if(v[i][j+1]) upd(T|(2<<y));continue;}if(p==2&&q==1){upd(T);continue;}if(p==1&&q==2&&i==nn&&j==mm){ans+=tag;continue;}if(p==1&&q==1){for(tmp=0,u=y+2;u<=m+m&&tmp>=0;tmp+=((T>>u)&1)-((T>>(u+1))&1),u+=2);u-=2,upd(T^(3<<u));continue;}if(p==2&&q==2){for(tmp=0,u=x-2;u>=0&&tmp>=0;tmp+=((T>>(u+1))&1)-((T>>u)&1),u-=2);u+=2,upd(T^(3<<u));continue;}}}for(t=1;t<=tot[k];t++) state[k][t]<<=2;}printf("%lld",ans);return 0; }

?

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

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【BZOJ1814】Ural 1519 Formula 1 插头DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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