误落迷宫2-题解（C++代码）

解题思路；广度优先搜索    广度优先搜索具有最短路性

注意事项:    搜索完T时注意 恢复标记     

参考代码:  新手  代码写的有点乱

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

 typedef long long ll;

const int N = 210;

char g[N][N];

int n, m;

bool v[N][N],c[N][N];

bool k;

struct node

{

    int x, y,d;

};

int x, y;

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

bool pd(int x,int y)

{

    return x >= 0 && x < n&& y >= 0 && y < m;

}

int bfs1(int x, int y)

{

    queue<node> q;

    q.push({ x,y,0 });

    v[x][y] = true;

    while (!q.empty())

    {

        node now = q.front();

        q.pop();

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

        {

            int dx = now.x + d[i][0];

            int dy = now.y + d[i][1];

            if (pd(dx, dy) && !v[dx][dy] && g[dx][dy] != '1')

            {

                if (g[dx][dy] == 'T')

                {

                    return now.d + 1;

                }

                else

                {

                    v[dx][dy] = true;

                    q.push({ dx,dy,now.d + 1 });

                }

            }

        }

    }

}

int bfs2(int x,int y)

{

    queue<node> q;

    q.push({x,y,0});

    c[x][y] = true;

    while (!q.empty())

    {

        node now = q.front();

        q.pop();

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

        {

            int dx = now.x + d[i][0];

            int dy = now.y + d[i][1];

            if (pd(dx, dy) && !c[dx][dy] && g[dx][dy] != '1')

            {

                if (g[dx][dy] == 'E')

                {

                    return now.d + 1;

                }

                else

                {

                    c[dx][dy] = true;

                    q.push({dx,dy,now.d+1});

                }

            }

        }

    }

}

int main()

{

    cin >> n >> m;

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

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

            cin >> g[i][j];

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

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

        {

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

            {

                x = i; y = j;

                break;

            }

        }int f = bfs1(x, y) ;

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

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

        {

            if (g[i][j] == 'T')

            {

                x = i; y = j;

                break;

            }

        }

    int r=bfs2(x,y);

    cout << f+r << endl;;

    return 0;

}