hdoj1180——诡异的楼梯

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1180
bfs,思路是贪心,如果遇到楼梯,能过则尽量过(对面未访问)。因为走楼梯不用花时间,相当于一分钟走了两步,将楼梯对面的格子(前提:还未访问)在解答树中的深度减小了。注意一种特殊情况,这也是本题的精华。就是说如果遇到楼梯,且对面未访问,但此时无法走过楼梯(楼梯方向不对,楼梯方向可以根据走的分钟数的奇偶性判断),则原地等待。等待的具体编程实现方式是bfs时将自身进队。如果下一分钟楼梯对面的格子=已被访问,则放弃,否则通过楼梯访问之。

#include<stdio.h>
#include<stdlib.h>
int a[5],b[5];
int iq=0;
typedef struct Queue{
    int x,y;
    int depth;
}Queue;
int main()
{
    int n,m;
    char map[25][25];
    a[1]=-1;b[1]=0;
    a[2]=0;b[2]=-1;
    a[3]=1;b[3]=0;
    a[4]=0;b[4]=1;
    while(scanf("%d %d",&n,&m)!=EOF)
    {

        getchar();
        int i,j,xs,ys,xd,yd;
        int visit[25][25];
        for(i=0;i<=n+1;i++)
            for(j=0;j<=m+1;j++)
                visit[i][j]=1;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%c",&map[i][j]);
                if(map[i][j]!='*')
                    visit[i][j]=0;
                if(map[i][j]=='S')
                {
                    xs=i;
                    ys=j;
                }
                if(map[i][j]=='T')
                {
                    xd=i;
                    yd=j;
                }
            }
            getchar();
        }
        iq=0;
        Queue queue[501];
        for(i=0;i<=500;i++)
        {
            queue[i].depth=0;
            queue[i].x=queue[i].y=0;
        }
        queue[iq].x=xs;
        queue[iq].y=ys;
        queue[iq++].depth=0;
        visit[xs][ys]=1;
        bool flag=false;
        for(i=0;i<=iq-1;i++)
        {
            for(j=1;j<=4;j++)
            {
                if(!visit[queue[i].x+a[j]][queue[i].y+b[j]])
                {
                    if(queue[i].x+a[j]==xd && queue[i].y+b[j]==yd)
                    {
                        queue[iq].x=queue[i].x+a[j];
                        queue[iq].y=queue[i].y+b[j];
                        queue[iq++].depth=queue[i].depth+1;
                        flag=true;
                        break;
                    }
                    else if(map[queue[i].x+a[j]][queue[i].y+b[j]]!='-' && map[queue[i].x+a[j]][queue[i].y+b[j]]!='|')
                    {
                        visit[queue[i].x+a[j]][queue[i].y+b[j]]=1;
                        queue[iq].x=queue[i].x+a[j];
                        queue[iq].y=queue[i].y+b[j];
                        queue[iq++].depth=queue[i].depth+1;
                    }
                    else
                    {
                        if(a[j]==-1 && b[j]==0)
                        {
                            if(!visit[queue[i].x+2*a[j]][queue[i].y+2*b[j]])
                            {
                                if((queue[i].depth%2==0 && map[queue[i].x+a[j]][queue[i].y+b[j]]=='|')||(queue[i].depth%2==1 && map[queue[i].x+a[j]][queue[i].y+b[j]]=='-'))
                                {
                                    visit[queue[i].x+2*a[j]][queue[i].y+2*b[j]]=1;
                                    queue[iq].x=queue[i].x+2*a[j];
                                    queue[iq].y=queue[i].y+2*b[j];
                                    queue[iq++].depth=queue[i].depth+1;
                                
                                }
                                else
                                {
                                    queue[iq].x=queue[i].x;
                                    queue[iq].y=queue[i].y;
                                    queue[iq++].depth=queue[i].depth+1;
                                
                                }
                            }
                        }
                        if(a[j]==0 && b[j]==-1)
                        {
                            if(!visit[queue[i].x+2*a[j]][queue[i].y+2*b[j]])
                            {
                                if((queue[i].depth%2==0 && map[queue[i].x+a[j]][queue[i].y+b[j]]=='-')||(queue[i].depth%2==1 && map[queue[i].x+a[j]][queue[i].y+b[j]]=='|'))
                                {
                                    visit[queue[i].x+2*a[j]][queue[i].y+2*b[j]]=1;
                                    queue[iq].x=queue[i].x+2*a[j];
                                    queue[iq].y=queue[i].y+2*b[j];
                                    queue[iq++].depth=queue[i].depth+1;
                                
                                }
                                else
                                {
                                    queue[iq].x=queue[i].x;
                                    queue[iq].y=queue[i].y;
                                    queue[iq++].depth=queue[i].depth+1;
                                
                                }
                            }
                        }

                        if(a[j]==1 && b[j]==0)
                        {
                            if(!visit[queue[i].x+2*a[j]][queue[i].y+2*b[j]])
                            {
                                if((queue[i].depth%2==0 && map[queue[i].x+a[j]][queue[i].y+b[j]]=='|')||(queue[i].depth%2==1 && map[queue[i].x+a[j]][queue[i].y+b[j]]=='-'))
                                {
                                    visit[queue[i].x+2*a[j]][queue[i].y+2*b[j]]=1;
                                    queue[iq].x=queue[i].x+2*a[j];
                                    queue[iq].y=queue[i].y+2*b[j];
                                    queue[iq++].depth=queue[i].depth+1;
                                
                                }
                                else
                                {
                                    queue[iq].x=queue[i].x;
                                    queue[iq].y=queue[i].y;
                                    queue[iq++].depth=queue[i].depth+1;
                                
                                }
                            }
                        }

                        if(a[j]==0 && b[j]==1)
                        {
                            if(!visit[queue[i].x+2*a[j]][queue[i].y+2*b[j]])
                            {
                                if((queue[i].depth%2==0 && map[queue[i].x+a[j]][queue[i].y+b[j]]=='-')||(queue[i].depth%2==1 && map[queue[i].x+a[j]][queue[i].y+b[j]]=='|'))
                                {
                                    visit[queue[i].x+2*a[j]][queue[i].y+2*b[j]]=1;
                                    queue[iq].x=queue[i].x+2*a[j];
                                    queue[iq].y=queue[i].y+2*b[j];
                                    queue[iq++].depth=queue[i].depth+1;
                                
                                }
                                else
                                {
                                    queue[iq].x=queue[i].x;
                                    queue[iq].y=queue[i].y;
                                    queue[iq++].depth=queue[i].depth+1;
                                
                                }
                            }
                        }
                    }
                }
            }
            if(flag)
                break;
        }
        printf("%d\n",queue[iq-1].depth);
    
    }

return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>