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;
}补充：软件开发 , C++ ,
