诡异的楼梯 HDU1180

时间:2021-11-16 20:35:06

这题做了很久

做好了感觉很简单。。。 现在做题思路更加清晰了

一个要点就是   当楼梯过不去的时候不能是先过去时间加2  必须得回去等一秒   否则queue的时间顺序会被打破

#include<bits/stdc++.h>
using namespace std; int sx,sy,ex,ey;int n,m;
char m1[][];
bool f[][]; struct node
{
int x,y,d;
node(int x=,int y=,int d=):x(x),y(y),d(d){}
}; void bfs()
{
memset(f,false,sizeof(f));
int dx[]={,,,-};
int dy[]={,,-,};
node u(sx,sy,);
queue<node>q;
q.push(u); while(!q.empty())
{
u=q.front();q.pop();
// printf("%d %d %d\n",u.x,u.y,u.d);
if(u.x==ex&&u.y==ey){printf("%d\n",u.d);return;} for(int i=;i<;i++)
{
node v(u.x+dx[i],u.y+dy[i],u.d+); if(v.x>=&&v.x<=n&&v.y>=&&v.y<=m&&m1[v.x][v.y]!='*')
{ if(m1[v.x][v.y]=='|')
{
if(i==||i==)//shuiping
{
if(v.d%==&&f[v.x+dx[i]][v.y+dy[i]]==false){v.x-=dx[i];v.y-=dy[i];q.push(v);} else if (v.d%==&&f[v.x+dx[i]][v.y+dy[i]]==false){v.x+=dx[i];v.y+=dy[i];q.push(v);} }
if(i==||i==)
{
if(v.d%==&&f[v.x+dx[i]][v.y+dy[i]]==false){v.x+=dx[i];v.y+=dy[i];f[v.x][v.y]=true;q.push(v);} else if (v.d%==&&f[v.x+dx[i]][v.y+dy[i]]==false){v.x-=dx[i];v.y-=dy[i];q.push(v);}
} } if(m1[v.x][v.y]=='-')
{
if(i==||i==)//shuiping
{
if(v.d%==&&f[v.x+dx[i]][v.y+dy[i]]==false){v.x+=dx[i];v.y+=dy[i];q.push(v);} else if (v.d%==&&f[v.x+dx[i]][v.y+dy[i]]==false){v.x-=dx[i];v.y-=dy[i];q.push(v);} }
if(i==||i==)
{
if(v.d%==&&f[v.x+dx[i]][v.y+dy[i]]==false){v.x-=dx[i];v.y-=dy[i];q.push(v);} else if (v.d%==&&f[v.x+dx[i]][v.y+dy[i]]==false){v.x+=dx[i];v.y+=dy[i];f[v.x][v.y]=true;q.push(v);}
} } else if(f[v.x][v.y]==false&&(m1[v.x][v.y]=='.'||v.x==ex&&v.y==ey))
{
f[v.x][v.y]=true;q.push(v);
} } } } } int main()
{ while(scanf("%d%d",&n,&m)==)
{
for(int i=;i<=n;i++)
{
scanf("%s",m1[i]+);
for(int j=;j<=m;j++)
{
if(m1[i][j]=='S'){sx=i;sy=j;}
if(m1[i][j]=='T'){ex=i;ey=j;} } } // printf("%d %d %d %d\n",sx,sy,ex,ey);
bfs();
//printf("pl"); } return ;
}