海南住房和城乡建设厅网站登陆,查看网站是用什么做的,seo视频教学网站,现在的网站建设用什么语言【BZOJ1814】Ural 1519 Formula 1 题意#xff1a;一个 m * n 的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。(n,m12) 题解#xff1a;插头DP板子题#xff0c;刷板子#xff0c;附带题解链接。 如何存放状态呢#xff1f;可以采用hash#xff0c;…【BZOJ1814】Ural 1519 Formula 1 题意一个 m * n 的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。(n,m12) 题解插头DP板子题刷板子附带题解链接。 如何存放状态呢可以采用hash我们的hash表形如一个队列每次新加入一个状态时就沿着这个状态在队列中对应的hash值不断向后找直到找到这个状态或者发现一个空位为止。 本题我的状态采用了4进制表示。 #include cstdio
#include cstring
#include iostream
using namespace std;
typedef long long ll;
const int limit99991;
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 posS%limit;while(hs[pos]){if(state[k][hs[pos]]S){dp[k][hs[pos]]tag;return ;}pos;if(poslimit) pos0;}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(i1;in;i){scanf(%s,str1);for(j1;jm;j)asdasd{v[i][j]str[j].;if(v[i][j]) nni,mmj;}}tot[0]1,state[0][1]0,dp[0][1]1;for(i1;in;i){for(j1;jm;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(t1;ttot[k^1];t){Sstate[k^1][t],tagdp[k^1][t],yj1,xy-2,p(Sx)3,q(Sy)3,TS^(px)^(qy);if(!v[i][j]){if(!p!q) upd(T);continue;}if(p0q0v[i][j1]v[i1][j]){upd(T|(1x)|(2y));continue;}if((p0q1)||(p1q0)){if(v[i1][j]) upd(T|(1x));if(v[i][j1]) upd(T|(1y));continue;}if((p0q2)||(p2q0)){if(v[i1][j]) upd(T|(2x));if(v[i][j1]) upd(T|(2y));continue;}if(p2q1){upd(T);continue;}if(p1q2innjmm){anstag;continue;}if(p1q1){for(tmp0,uy2;ummtmp0;tmp((Tu)1)-((T(u1))1),u2);u-2,upd(T^(3u));continue;}if(p2q2){for(tmp0,ux-2;u0tmp0;tmp((T(u1))1)-((Tu)1),u-2);u2,upd(T^(3u));continue;}}}for(t1;ttot[k];t) state[k][t]2;}printf(%lld,ans);return 0;
} 转载于:https://www.cnblogs.com/CQzhangyu/p/8010738.html
