台湾菜

HDOJ 1180

twcai • acm/icpc

诡异的楼梯,一道蛮单纯的广搜题,不过我觉得有些细节还是比较值得注意的(我忽略了过楼梯后的若干情况)。
相对其他换汤不换药的迷宫来说,蛮有意思。
#include
#include
using namespace std;

char ma[22][22];
int hash[22][22];
int dir[4][2]={0,1,-1,0,0,-1,1,0};
int n,m;
struct node{
int ni;
int nj;
int t;
};
node now,next;
priority_queue hp;

inline bool operator<(const node &x,const node &y)
{
return x.t>y.t;
}

inline bool valid(const node &x)
{
return (x.ni>=0 && x.nj>=0 && x.ni }

inline int bfs()
{
int i;
int sd;
while(!hp.empty()) hp.pop();
memset(hash,0,sizeof(hash));
hash[now.ni][now.nj]=1;
hp.push(now);
while(!hp.empty())
{
now=hp.top();hp.pop();
if(ma[now.ni][now.nj]=='T')
return now.t;
for(i=0;i<4;i++)
{
next.ni=now.ni+dir[i][0];
next.nj=now.nj+dir[i][1];
if(!valid(next) || ma[next.ni][next.nj]=='*') continue;
if(hash[next.ni][next.nj]) continue;
if(ma[next.ni][next.nj]=='T' || ma[next.ni][next.nj]=='.')
{
next.t=now.t+1;
hp.push(next);
hash[next.ni][next.nj]=1;
continue;
}

if(ma[next.ni][next.nj]=='-' && (i&1)==0)
sd=1;
else if(ma[next.ni][next.nj]=='|' && (i&1)==1)
sd=1;
else sd=0;
next.ni+=dir[i][0];
next.nj+=dir[i][1];
if(!valid(next) || ma[next.ni][next.nj]=='*') continue;
if(hash[next.ni][next.nj]) continue;
if(((now.t&1)==0 && sd==1) || ((now.t&1)==1 && sd==0))
next.t=now.t+1;
else
next.t=now.t+2;
hash[next.ni][next.nj]=1;
hp.push(next);
}
}
return 0;
}

int main()
{
bool flag;
int i,j,ret;
while(scanf("%d %d",&n,&m)!=EOF)
{
getchar(); flag=0;
for(i=0;i {
gets(ma[i]);
for(j=0;j if(ma[i][j]=='S'){
now.ni=i;
now.nj=j;
now.t=0;
flag=1;
}
}
ret=bfs();
printf("%dn",ret);
}
return 0;
}

comments powered by Disqus