迷宫2----BFS

题目 :
蒜头君在你的帮助下终于逃出了迷宫，但是蒜头君并没有沉浸于喜悦之中，而是很快的又陷入了思考，从这个迷宫逃出的最少步数是多少呢？
输入格式
第一行输入两个整数 n 和 m，表示这是一个 n×m 的迷宫。
接下来的输入一个 n 行 m 列的迷宫。其中 ‘S’表示蒜头君的位置，’‘表示墙，蒜头君无法通过，’.‘表示路，蒜头君可以通过’.'移动，'T’表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。
输出格式
输出整数，表示蒜头君逃出迷宫的最少步数，如果蒜头君无法逃出迷宫输出 −1。
数据范围
1≤n,m≤10。
输出时每行末尾的多余空格，不影响答案正确性

样例输入1

3 4

S**.

..*.

***T

样例输出1

-1

样例输入2

3 4

S**.

....

***T

样例输出2

5

代码：

#include<iostream>

#include<queue>

using namespace std;

struct Node

{

    int x,y,step;

    Node(int xx,int yy,int ss):x(xx),y(yy),step(ss){ }

};

queue<Node>q;

bool mark[20][20];

int n,m,beginx,beginy,endx,endy,step=0;

char map[20][20];

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

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

//限界函数

bool check(int r,int c){

    if (r>=0&&r<n&&c>=0&&c<m)

        return true;

    return false;

}

void BFS(int r,int c){

    //第一步，先把起始点放入queue，设置层数step=0

    q.push(Node(r,c,0));

    //第二步，查找，队列非空就有机会找到

    while (!q.empty())

    {

        //第三步，取对头

        Node s = q.front();

        //找到即可退出

        if (s.x==endx&&s.y==endy)

        {

            cout<<s.step<<endl;

            return ;

        }else

        {

            //遍历子节点

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

            {

                int newx=s.x+dx[i];

                int newy = s.y+dy[i];

                //判断子节点是否可以通过，可通过则压栈，设置已访问

                if (check(newx,newy)&&!mark[newx][newy]&&map[newx][newy]!='*')

                {

                    mark[newx][newy]=true;

                    q.push(Node(newx,newy,s.step+1));

                }

            }

        }

        q.pop();

    }

    cout<<"-1"<<endl;

    return;

}

int main(){

    cin>>n>>m;

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

    {

        cin>>map[i];

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

        {

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

            {

                beginx= i;

                beginy=j;

            }else if (map[i][j]=='T')

            {

                endx= i;

                endy=j;

            }

        }

    }

    BFS(beginx,beginy);

}

巴特西

迷宫2----BFS

样例输入1

样例输出1

样例输入2

样例输出2

最新文章

热门文章