SDJZUOJ迷宫问题

题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。

输入格式

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。

输出

对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

1
5 5
S-###
-----
##---
E#---
---##

样例输出

分析：
BFS入门

源码：

#include<stdio.h>

#include<string.h>

#include<queue>

#include<iostream>

using namespace std;

struct N  //结构体定义了2个信息:

{

    int x,y;  //结点编号

    int step;  //步数

} p[105];

char map[105][105];

int vis[105][105];

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

int n,m,sx,sy,ex,ey,ans;

bool check(int x,int y)

{

    if(x>=0 && x<m && y>=0 && y<n&&vis[x][y]==0&& map[x][y]!='#')

        return true;

    return false;

}

void bfs()

{

    queue<N> Q;//定义一个队列

    N a;

    N next;

    a.x = sx;

    a.y = sy;

    a.step = 0;//结点编号、步数初始化

    vis[a.x][a.y]=1;//记录此结点是否遍历过

    Q.push(a);//起始点放入队列

    while(!Q.empty())//当队列不为空

    {

        a = Q.front();//取出队头结点

        Q.pop();

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

        {

            next = a;

            next.x+=dir[i][0];

            next.y+=dir[i][1];

            next.step++;    //向其余方向遍历

            if(next.x==ex&&next.y==ey)//若它是所求的目标状态，跳出循环

            {

                ans = next.step;

                return ;

            }

            if(check(next.x,next.y))

            {

                next.step=a.step+1;

                vis[next.x][next.y] = 1;

                Q.push(next);//扩展出子结点、依次添到到队尾

            }

        }

    }

    ans = -1;//找不到目标、输出-1.

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        memset(vis,0,sizeof(vis));

        scanf("%d%d",&m,&n);

        int i,j;

        for(i = 0; i<m; i++)

            for(j=0; j<n; j++)

                cin>>map[i][j];

        for(i = 0; i<m; i++)

            for(j = 0; j<n; j++)

            {

                if(map[i][j]=='S')

                {

                    sx = i;

                    sy = j;

                    //标记起始位置

                }

                else if(map[i][j]=='E')

                {

                    ex=i;

                    ey=j;

                }

            }

        bfs();

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

    }

    return 0;

}

巴特西

SDJZUOJ迷宫问题

题目描述

输入格式

输出

样例输入

样例输出

最新文章

热门文章