1672: 迷宫问题(记模型，以后遇到直接用)

解题思路:

注意事项:

参考代码:

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

struct node

{

    int x, y;

}t;

queue <node> q;

int dx[] = {0, 0, -1, 1};           //位移方向

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

int main()

{

    bool a[105][105];   //0为未走过，1为走过或者障碍

    int T;

    cin>>T;

    while(T--)

    {

        int m, n;

        cin>>m>>n;          //行 列

        memset(a, 0, sizeof(a));

        int x0, y0, x1, y1;

        char temp;

        for (int i = 1; i <= m; i++)

        {

            for (int j = 1; j <= n; j++)

            {

                cin >> temp;

                if (temp == 'S') x0 = i, y0 = j;

                if (temp == 'E') x1 = i, y1 = j;

                if (temp == '#') a[i][j] = 1;

            }

        }    

        //开始广度优先遍历咯

        int s = 0;          //计算步数

        a[x0][y0] = 1;

        q.push(node({x0, y0}));         //起点入队

        bool flag = 1;      //用以区分是队空还是找到终点，退出循环的

        while (!q.empty() && flag)         //寻找是队空还是找到终点

        {

            s++;

            int size = q.size();

            for (int i = 1; i <= size; i++)

            {

                t = q.front();          //取队头

                q.pop();                //删队头

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

                {

                    int x = t.x + dx[j];

                    int y = t.y + dy[j];

                    if (x >= 1 && x <= m && y >= 1 && y <= n && a[x][y] == 0)

                    {

                        a[x][y] = 1;

                        if (x == x1 && y == y1) flag = 0;          //到终点了

                        else q.push(node({x, y}));              //新点入队

                    }

                }

            }

        }

        if (!flag) cout<<s<<endl;

        else cout<<-1<<endl;

    }

    return 0;

}