hdu 1732 Push Box

http://acm.hdu.edu.cn/showproblem.php?pid=1732

推箱子和游戏规则一样。

 #include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; char g[][];
int n,m;
int sx,sy;
bool vis[][][][][][][][];
int dir[][]= {{,},{,-},{,},{-,}};
struct node
{
int x[],y[],xx,yy,step;
} st1,st2,st; int deal(node p,int i,int pos)
{
p.xx+=dir[i][];
p.yy+=dir[i][];
if(p.xx>=&&p.xx<n&&p.yy>=&&p.yy<m)
{
for(int j=; j<; j++)
{
if(j!=pos&&p.x[j]==p.xx&&p.y[j]==p.yy)
{
return ;
}
}
return ;
}
return ;
} int bfs()
{
queue<node>q;
st.step=;
st.xx=sx;
st.yy=sy;
q.push(st);
memset(vis,false,sizeof(vis));
vis[sx][sy][st.x[]][st.y[]][st.x[]][st.y[]][st.x[]][st.y[]]=true;
while(!q.empty())
{
st1=q.front();
q.pop();
int cnt=;
for(int i=; i<; i++)
{
if(g[st1.x[i]][st1.y[i]]=='@')
{
cnt++;
}
}
if(cnt==)
{
return st1.step;
}
for(int i=; i<; i++)
{
st2=st1;
st2.xx=st2.xx+dir[i][];
st2.yy=st2.yy+dir[i][];
st2.step++;
if(st2.xx>=&&st2.xx<n&&st2.yy>=&&st2.yy<m&&g[st2.xx][st2.yy]!='#')
{
int pos;
for(pos=; pos<; pos++)
{
if(st2.x[pos]==st2.xx&&st2.y[pos]==st2.yy)
{
break;
}
}
if(pos<)
{
if(deal(st2,i,pos))
{
st2.x[pos]+=dir[i][];
st2.y[pos]+=dir[i][];
if(!vis[st2.xx][st2.yy][st2.x[]][st2.y[]][st2.x[]][st2.y[]][st2.x[]][st2.y[]])
{
vis[st2.xx][st2.yy][st2.x[]][st2.y[]][st2.x[]][st2.y[]][st2.x[]][st2.y[]]=true;
q.push(st2);
}
}
}
else
{
if(!vis[st2.xx][st2.yy][st2.x[]][st2.y[]][st2.x[]][st2.y[]][st2.x[]][st2.y[]])
{
vis[st2.xx][st2.yy][st2.x[]][st2.y[]][st2.x[]][st2.y[]][st2.x[]][st2.y[]]=true;
q.push(st2);
}
}
}
}
}
return -;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int num=;
for(int i=; i<n; i++)
{
scanf("%s",g[i]);
for(int j=; j<m; j++)
{
if(g[i][j]=='X')
{
g[i][j]='.';
sx=i;
sy=j;
}
else if(g[i][j]=='*')
{
g[i][j]='.';
st.x[num]=i;
st.y[num]=j;
num++;
}
}
}
printf("%d\n",bfs());
}
return ;
}
上一篇:[BUAA软工]第零次博客作业---问题回答


下一篇:jQuery 动画之 添加商品到购物车