POJ 1324 Holedox Moving 搜索

優先隊列---A*的估價函數不能為蛇頭到(1,1)的距離，這樣會出錯。

看了discuss，有大神說這題A*的估價函數為BFS (0,0)到各點的花費在乘上10 ，但是還是不清楚，希望知道的可以給我留個言，謝謝了。

思路：

用0,1,2,3表示方向，這樣就可以用四進制狀態壓縮了。

總共需要3+3*4^1+……3*4^6.

推薦大家能不用STL就不用STL，太浪費時間了。

下面是用STL超時代碼和用數組模擬AC代碼。

超時代碼：

#include <iostream>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <cstring>  
#include <string>  
#include <vector>  
#include <list>  
#include <deque>  
#include <queue>  
#include <iterator>  
#include <stack>  
#include <map>  
#include <set>  
#include <algorithm>  
#include <cctype>  
using namespace std; 
 
typedef long long LL; 
const int N=21; 
const LL II=1000000007; 
 
int n,m,L; 
int maps[N][N];//0代表空，1代表蛇身體，2代表石頭  
bool vis[N][N][17000];//狀態壓縮  
int t[4][2]={0,-1,1,0,0,1,-1,0}; 
 
struct xh 
{ 
    int step; 
    int po[11][2]; 
}w,e; 
 
int location(int px,int py,int nx,int ny)//求兩個節點的相對位置  
{ 
    if(px==nx) 
    { 
        if(py>ny) 
            return 0; 
        else 
            return 1; 
    } 
    else 
    { 
        if(px>nx) 
            return 2; 
        else 
            return 3; 
    } 
} 
 
int gethash(int B[][2]) 
{//得到狀態  
    int s=0; 
    for(int i=0;i<L-1;i++) 
        s=s*4+location(B[i][0],B[i][1],B[i+1][0],B[i+1][1]); 
    return s; 
} 
 
bool inmap(int x,int y,xh a) 
{ 
    if(!(x>=1&&x<=n&&y>=1&&y<=m)) 
        return false; 
    if(maps[x][y]==2) 
        return false; 
    for(int i=0;i<L;i++)//蛇頭和蛇尾相連也不行的  
        if(x==a.po[i][0]&&y==a.po[i][1])//判斷是否這一步為蛇身  
            return false; 
    return true; 
} 
 
void bfs() 
{ 
    int i,j,hash,x,y; 
    w.step=0; 
    hash=gethash(w.po); 
    x=w.po[0][0];    y=w.po[0][1]; 
    vis[x][y][hash]=true; 
    queue<xh> q; 
    q.push(w); 
    if(x==1&&y==1) 
    { 
        printf("0\n"); 
        return ; 
    } 
    while(!q.empty()) 
    { 
        e=q.front(); 
        q.pop(); 
        for(i=0;i<4;i++) 
        { 
            w=e; 
            x=w.po[0][0];    y=w.po[0][1]; 
            x+=t[i][0];     y+=t[i][1]; 
            if(!inmap(x,y,w)) continue; 
            for(j=L-1;j>=1;j--) 
            { 
                w.po[j][0]=w.po[j-1][0]; 
                w.po[j][1]=w.po[j-1][1]; 
            } 
            w.po[0][0]=x;    w.po[0][1]=y; 
            hash=gethash(w.po); 
            if(vis[x][y][hash]) continue; 
            vis[x][y][hash]=true; 
            w.step++; 
            q.push(w); 
            if(x==1&&y==1) 
            { 
                printf("%d\n",w.step); 
                return ; 
            } 
        } 
    } 
    printf("-1\n"); 
} 
 
int main() 
{ 
    int i,k,ci=0; 
    while(scanf("%d%d%d",&n,&m,&L)&&(n+m+L)) 
    { 
        memset(maps,0,sizeof(maps)); 
        memset(vis,false,sizeof(vis)); 
        for(i=0;i<L;i++) 
        { 
            scanf("%d%d",&w.po[i][0],&w.po[i][1]); 
        } 
        scanf("%d",&k); 
        while(k--) 
        { 
            int a,b; 
            scanf("%d%d",&a,&b); 
            maps[a][b]=2;//石頭  
        } 
        printf("Case %d: ",++ci); 
        bfs(); 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef long long LL;
const int N=21;
const LL II=1000000007;

int n,m,L;
int maps[N][N];//0代表空，1代表蛇身體，2代表石頭
bool vis[N][N][17000];//狀態壓縮
int t[4][2]={0,-1,1,0,0,1,-1,0};

struct xh
{
    int step;
    int po[11][2];
}w,e;

int location(int px,int py,int nx,int ny)//求兩個節點的相對位置
{
    if(px==nx)
    {
        if(py>ny)
            return 0;
        else
            return 1;
    }
    else
    {
        if(px>nx)
            return 2;
        else
            return 3;
    }
}

int gethash(int B[][2])
{//得到狀態
    int s=0;
    for(int i=0;i<L-1;i++)
        s=s*4+location(B[i][0],B[i][1],B[i+1][0],B[i+1][1]);
    return s;
}

bool inmap(int x,int y,xh a)
{
    if(!(x>=1&&x<=n&&y>=1&&y<=m))
        return false;
    if(maps[x][y]==2)
        return false;
    for(int i=0;i<L;i++)//蛇頭和蛇尾相連也不行的
        if(x==a.po[i][0]&&y==a.po[i][1])//判斷是否這一步為蛇身
            return false;
    return true;
}

void bfs()
{
    int i,j,hash,x,y;
    w.step=0;
    hash=gethash(w.po);
    x=w.po[0][0];    y=w.po[0][1];
    vis[x][y][hash]=true;
    queue<xh> q;
    q.push(w);
    if(x==1&&y==1)
    {
        printf("0\n");
        return ;
    }
    while(!q.empty())
    {
        e=q.front();
        q.pop();
        for(i=0;i<4;i++)
        {
            w=e;
            x=w.po[0][0];    y=w.po[0][1];
            x+=t[i][0];     y+=t[i][1];
            if(!inmap(x,y,w)) continue;
            for(j=L-1;j>=1;j--)
            {
                w.po[j][0]=w.po[j-1][0];
                w.po[j][1]=w.po[j-1][1];
            }
            w.po[0][0]=x;    w.po[0][1]=y;
            hash=gethash(w.po);
            if(vis[x][y][hash]) continue;
            vis[x][y][hash]=true;
            w.step++;
            q.push(w);
            if(x==1&&y==1)
            {
                printf("%d\n",w.step);
                return ;
            }
        }
    }
    printf("-1\n");
}

int main()
{
    int i,k,ci=0;
    while(scanf("%d%d%d",&n,&m,&L)&&(n+m+L))
    {
        memset(maps,0,sizeof(maps));
        memset(vis,false,sizeof(vis));
        for(i=0;i<L;i++)
        {
            scanf("%d%d",&w.po[i][0],&w.po[i][1]);
        }
        scanf("%d",&k);
        while(k--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            maps[a][b]=2;//石頭
        }
        printf("Case %d: ",++ci);
        bfs();
    }
    return 0;
}

 

 

用STL寫就超時了，用數組模擬就過了

AC代碼：

#include <iostream>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <cstring>  
#include <string>  
#include <vector>  
#include <list>  
#include <deque>  
#include <queue>  
#include <iterator>  
#include <stack>  
#include <map>  
#include <set>  
#include <algorithm>  
#include <cctype>  
using namespace std; 
 
typedef long long LL; 
const int N=21; 
const LL II=1000000007; 
 
int n,m,L; 
int maps[N][N];//0代表空，1代表蛇身體，2代表石頭  
bool vis[N][N][17000];//狀態壓縮  
int t[4][2]={0,-1,1,0,0,1,-1,0}; 
 
struct xh 
{ 
    int step; 
    int po[11][2]; 
}w,e,q[5000004]; 
 
int location(int px,int py,int nx,int ny)//求兩個節點的相對位置  
{ 
    if(px==nx) 
    { 
        if(py>ny) 
            return 0; 
        else 
            return 1; 
    } 
    else 
    { 
        if(px>nx) 
            return 2; 
        else 
            return 3; 
    } 
} 
 
int gethash(int B[][2]) 
{//得到狀態  
    int s=0; 
    for(int i=0;i<L-1;i++) 
        s=s*4+location(B[i][0],B[i][1],B[i+1][0],B[i+1][1]); 
    return s; 
} 
 
bool inmap(int x,int y,xh a) 
{ 
    if(!(x>=1&&x<=n&&y>=1&&y<=m)) 
        return false; 
    if(maps[x][y]==2) 
        return false; 
    for(int i=0;i<L;i++)//蛇頭和蛇尾相連也不行的  
        if(x==a.po[i][0]&&y==a.po[i][1])//判斷是否這一步為蛇身  
            return false; 
    return true; 
} 
 
void bfs() 
{ 
    int i,j,hash,x,y,head=0,tail=0; 
    w.step=0; 
    hash=gethash(w.po); 
    x=w.po[0][0];    y=w.po[0][1]; 
    vis[x][y][hash]=true; 
    q[tail++]=w; 
    if(x==1&&y==1) 
    { 
        printf("0\n"); 
        return ; 
    } 
    while(head<tail) 
    { 
        e=q[head++]; 
        for(i=0;i<4;i++) 
        { 
            w=e; 
            x=w.po[0][0];    y=w.po[0][1]; 
            x+=t[i][0];     y+=t[i][1]; 
            if(!inmap(x,y,w)) continue; 
            for(j=L-1;j>=1;j--) 
            { 
                w.po[j][0]=w.po[j-1][0]; 
                w.po[j][1]=w.po[j-1][1]; 
            } 
            w.po[0][0]=x;    w.po[0][1]=y; 
            hash=gethash(w.po); 
            if(vis[x][y][hash]) continue; 
            vis[x][y][hash]=true; 
            w.step++; 
            q[tail++]=w; 
            if(x==1&&y==1) 
            { 
                printf("%d\n",w.step); 
                return ; 
            } 
        } 
    } 
    printf("-1\n"); 
} 
 
int main() 
{ 
    int i,k,ci=0; 
    while(scanf("%d%d%d",&n,&m,&L)&&(n+m+L)) 
    { 
        memset(maps,0,sizeof(maps)); 
        memset(vis,false,sizeof(vis)); 
        for(i=0;i<L;i++) 
        { 
            scanf("%d%d",&w.po[i][0],&w.po[i][1]); 
        } 
        scanf("%d",&k); 
        while(k--) 
        { 
            int a,b; 
            scanf("%d%d",&a,&b); 
            maps[a][b]=2;//石頭  
        } 
        printf("Case %d: ",++ci); 
        bfs(); 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef long long LL;
const int N=21;
const LL II=1000000007;

int n,m,L;
int maps[N][N];//0代表空，1代表蛇身體，2代表石頭
bool vis[N][N][17000];//狀態壓縮
int t[4][2]={0,-1,1,0,0,1,-1,0};

struct xh
{
    int step;
    int po[11][2];
}w,e,q[5000004];

int location(int px,int py,int nx,int ny)//求兩個節點的相對位置
{
    if(px==nx)
    {
        if(py>ny)
            return 0;
        else
            return 1;
    }
    else
    {
        if(px>nx)
            return 2;
        else
            return 3;
    }
}

int gethash(int B[][2])
{//得到狀態
    int s=0;
    for(int i=0;i<L-1;i++)
        s=s*4+location(B[i][0],B[i][1],B[i+1][0],B[i+1][1]);
    return s;
}

bool inmap(int x,int y,xh a)
{
    if(!(x>=1&&x<=n&&y>=1&&y<=m))
        return false;
    if(maps[x][y]==2)
        return false;
    for(int i=0;i<L;i++)//蛇頭和蛇尾相連也不行的
        if(x==a.po[i][0]&&y==a.po[i][1])//判斷是否這一步為蛇身
            return false;
    return true;
}

void bfs()
{
    int i,j,hash,x,y,head=0,tail=0;
    w.step=0;
    hash=gethash(w.po);
    x=w.po[0][0];    y=w.po[0][1];
    vis[x][y][hash]=true;
    q[tail++]=w;
    if(x==1&&y==1)
    {
        printf("0\n");
        return ;
    }
    while(head<tail)
    {
        e=q[head++];
        for(i=0;i<4;i++)
        {
            w=e;
            x=w.po[0][0];    y=w.po[0][1];
            x+=t[i][0];     y+=t[i][1];
            if(!inmap(x,y,w)) continue;
            for(j=L-1;j>=1;j--)
            {
                w.po[j][0]=w.po[j-1][0];
                w.po[j][1]=w.po[j-1][1];
            }
            w.po[0][0]=x;    w.po[0][1]=y;
            hash=gethash(w.po);
            if(vis[x][y][hash]) continue;
            vis[x][y][hash]=true;
            w.step++;
            q[tail++]=w;
            if(x==1&&y==1)
            {
                printf("%d\n",w.step);
                return ;
            }
        }
    }
    printf("-1\n");
}

int main()
{
    int i,k,ci=0;
    while(scanf("%d%d%d",&n,&m,&L)&&(n+m+L))
    {
        memset(maps,0,sizeof(maps));
        memset(vis,false,sizeof(vis));
        for(i=0;i<L;i++)
        {
            scanf("%d%d",&w.po[i][0],&w.po[i][1]);
        }
        scanf("%d",&k);
        while(k--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            maps[a][b]=2;//石頭
        }
        printf("Case %d: ",++ci);
        bfs();
    }
    return 0;
}