POJ 1198 / HDU 1401 Solitaire (记忆化搜索+meet in middle)

题目大意：给你一个8*8的棋盘，上面有四个棋子，给你一个初始排布，一个目标排布，每次移动，可以把一个棋子移动到一个相邻的空位，或者跨过1个相邻的棋子，在保证棋子移动不超过8次的情况下，问能否把棋盘上的棋子由初始排布变成目标排布

8*8的棋盘，刚好不爆ull，状压那些位置有棋子

然后从初始状态开始，暴搜出当前状态下，移动一个棋子之后所有可能到达的状态

直接搜，总状态数是8^8，此外还有常数，会爆

由于给定了目标排布，考虑meet in middle

从起始状态和目标状态各搜4步即可

为了防止爆栈，同时为了好写好调，最好用bfs

具体实现呢，可以开两个队列正反同时bfs，搜到合法结果就break掉，可以减少很多常数

开2个map，表示正/反着跑能否到达状态s，如果能到达，则mp[s]=1

以正着搜为例，当前从que1中取出的状态为s，能到达的下一个状态为t，如果t出现在map1中，就不必在推入que1了，如果t出现在map2中，说明存在合法状态，break掉输出YES

代码好长啊..但在搜索题里算短的了

 #include <map>

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define NN 5010

 #define MM 2000

 #define maxn 200

 #define ll long long

 #define uint unsigned int

 #define ull unsigned long long

 using namespace std;

 int id[][];

 int xx[]={-,,,};

 int yy[]={,,,-};

 ull bin[];

 int ax[],ay[],bx[],by[];

 struct node{

     ull s;int c;

     friend bool operator < (const node &s1,const node &s2)

         {return s1.s<s2.s;}

     node(ull s,int c):s(s),c(c){}

     node(){}

 };

 map<ull,int>mp[];

 int check(int x,int y,ull s)

 {

     if(x<||y<||x>||y>)return ;

     if(s&bin[id[x][y]]) return ;

     return ;

 }

 int main()

 {

     //freopen("t2.in","r",stdin);

     for(int i=;i<=;i++)

         for(int j=;j<=;j++)

             id[i][j]=*(i-)+j-;

             //px[id[i][j]]=i,py[id[i][j]]=j;

     bin[]=;

     for(int i=;i<=;i++)

         bin[i]=bin[i-]<<;

     while(scanf("%d%d%d%d",&ax[],&ay[],&ax[],&ay[])!=EOF)

     {

     scanf("%d%d%d%d",&ax[],&ay[],&ax[],&ay[]);

     scanf("%d%d%d%d",&bx[],&by[],&bx[],&by[]);

     scanf("%d%d%d%d",&bx[],&by[],&bx[],&by[]);

     queue<node>q[];

     ull s=,t=;

     int cnt=,fx,fy,fl,nt;

     for(int i=;i<=;i++)

         s|=bin[id[ax[i]][ay[i]]];

     mp[][s]=;

     q[].push(node(s,));s=;

     for(int i=;i<=;i++)

         s|=bin[id[bx[i]][by[i]]];

     mp[][s]=;

     q[].push(node(s,));

     int ans=,c,x,y;

     while((!q[].empty()||!q[].empty())&&!ans)

     {

         if(!q[].empty())

         {

         node K=q[].front();q[].pop();

         s=K.s,c=K.c;

         for(int i=;i<=;i++)

         for(int j=;j<=;j++)

         {

             if(!(s&bin[id[i][j]])) continue;

             for(int k=;k<;k++)

             {

                 x=i+xx[k],y=j+yy[k];

                 fl=check(x,y,s);

                 if(!fl) continue;

                 if(fl==){

                     x+=xx[k],y+=yy[k];

                     if(check(x,y,s)!=) continue;

                 }

                 t=(s^bin[id[i][j]])|bin[id[x][y]];

                 if(mp[].find(t)!=mp[].end())

                     continue;

                 if(mp[].find(t)!=mp[].end())

                     {ans=;break;}

                 mp[][t]=;

                 if(c<) q[].push(node(t,c+));

                 if(ans==) break;

             }

         }

         }

         if(!q[].empty())

         {

         node K=q[].front();q[].pop();

         s=K.s,c=K.c;

         for(int i=;i<=;i++)

         for(int j=;j<=;j++)

         {

             if(!(s&bin[id[i][j]])) continue;

             for(int k=;k<;k++)

             {

                 x=i+xx[k],y=j+yy[k];

                 fl=check(x,y,s);

                 if(!fl) continue;

                 if(fl==){

                     x+=xx[k],y+=yy[k];

                     if(check(x,y,s)!=) continue;

                 }

                 t=(s^bin[id[i][j]])|bin[id[x][y]];

                 if(mp[].find(t)!=mp[].end())

                     continue;

                 if(mp[].find(t)!=mp[].end())

                     {ans=;break;}

                 mp[][t]=;

                 if(c<) q[].push(node(t,c+));

                 if(ans==) break;

             }

         }

         }

     }

     if(ans==)

         printf("YES\n");

     else

         printf("NO\n");

     mp[].clear();

     mp[].clear();

     }

     return ;

 }

巴特西

POJ 1198 / HDU 1401 Solitaire (记忆化搜索+meet in middle)

最新文章

热门文章