POJ 1324 Holedox Moving 搜索 - c++编程基础

优先队列---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   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
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=1&&x<=n&&y>=1&&y<=m)) 
        return false; 
    if(maps[x][y]==2) 
        return false; 
    for(int i=0;i 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
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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=1&&x<=n&&y>=1&&y<=m))
        return false;
    if(maps[x][y]==2)
        return false;
    for(int i=0;i 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 
 用STL写就超时了，用数组模拟就过了 
 AC代码： 
 
   
 #include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
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,i

POJ 1324 Holedox Moving 搜索 (一)