NYOJ-58最少步数，广搜思想！

最少步数

时间限制：3000 ms | 内存限制：65535 KB

难度：4

-> Link <-

这个题深搜广搜都是可以的，迷宫已经给出了，就看怎么做了；一般起点终点确定用广搜求最短路径问题；

广搜就用到队列了，将起点周围的可行的点都加入队列，在从队列中选取点又重复刚才的操作，直到找到终点；

可以用二维数组存起点到此点的最短路径，起点的路径为0；从队列里拿出一个点，其周围可行的点的路径便是这个点的路径加一，一直广搜到终点

#include<bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f;

int MAP[9][9]=

{

    1,1,1,1,1,1,1,1,1,

    1,0,0,1,0,0,1,0,1,

    1,0,0,1,1,0,0,0,1,

    1,0,1,0,1,1,0,1,1,

    1,0,0,0,0,1,0,0,1,

    1,1,0,1,0,1,0,0,1,

    1,1,0,1,0,1,0,0,1,

    1,1,0,1,0,0,0,0,1,

    1,1,1,1,1,1,1,1,1,

};

int sx,sy,gx,gy;

typedef pair<int,int>P;

int d[9][9];

int dx[4]={0,0,-1,1};

int dy[4]={1,-1,0,0};

void init()

{

    for(int i=0;i<=8;i++)

        for(int j=0;j<=8;j++)

        d[i][j]=INF;

}

int bfs()

{

    queue<P>q;

    q.push(P(sx,sy));

    d[sx][sy]=0;

    while(!q.empty())

    {

        P p=q.front();

        q.pop();

        if(p.first==gx&&p.second==gy) break;

        for(int i=0;i<4;i++)

        {

            int xx=p.first+dx[i];

            int yy=p.second+dy[i];

            if(xx>=0&&xx<=8&&yy>=0&&yy<=8&&!MAP[xx][yy]&&d[xx][yy]==INF)

            {

                q.push(P(xx,yy));

                d[xx][yy]=d[p.first][p.second]+1;

            }

        }

    }

    return d[gx][gy];

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d%d%d",&sx,&sy,&gx,&gy);

        init();

        printf("%d\n",bfs());

    }

    return 0;

}

巴特西

NYOJ-58最少步数，广搜思想！

最少步数

最新文章

热门文章