首页 > 其他 > 详细

【转】POJ-3984-迷宫问题:简单BFS

时间:2015-07-27 00:05:25      阅读:287      评论:0      收藏:0      [点我收藏+]

思路请点这里

如果一开始做这道题我应该不会马上想到用BFS做,我还在纠结如何判断路径最短,好在之前做过类似的不容易看出是BFS解的,做这道题时也就明白了广搜的结果就是最短路径

这大概就是 题做多了的缘故罢

#include<iostream>
#include<cstring>
using namespace std;

struct Node
{
        int x, y;
        int Par;
}Que[25];

int Visited[5][5];
int DirX[4] = {1, -1, 0, 0};
int DirY[4] = { 0, 0, 1, -1 };
int Front=0, Rear=1; // 自定义队列的头尾指针

void Print( int Point )
{
        if( Point != -1 )
        {
                Print( Que[Point].Par );
                cout<<"("<<Que[Point].x<<", "<<Que[Point].y<<")"<<endl;
        }
}

void BFS( int x, int y )
{
        while( Front < Rear )
        {
                if( Que[Front].x==4 && Que[Front].y==4 )
                    Print(Front);

                for( int i=0; i<4; i++ )
                {
                        int a = Que[Front].x + DirX[i];
                        int b = Que[Front].y + DirY[i];

                        if( a<0 || a>4 || b<0 || b>4 || Visited[a][b] )
                            continue;
                        else//入队
                        {
                                Visited[a][b]=1;
                                Que[Rear].x = a;
                                Que[Rear].y = b;
                                Que[Rear].Par = Front;
                                Rear++;
                        }
                }
                Front++;// 出队
        }
}

int  main()
{
        //memset( Visited, 0, sizeof(Visited) );
        for( int i=0; i<5; i++ )
            for( int j=0; j<5; j++ )
                cin>>Visited[i][j];

        Que[0].x=Que[0].y=0;
        Que[0].Par = -1;
        BFS(0, 0);

        return 0;
}

  

【转】POJ-3984-迷宫问题:简单BFS

原文:http://www.cnblogs.com/FightForCMU/p/4678991.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!