广度优先搜索BFS（cx14c）

解题思路:参考广度优先搜索BFS（cx14b）
注意事项:因为是多组数据，记得清空visited[N][N],即 memset(visited, 0, sizeof(visited));
参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N=105;

int r,c,n;

char mp[N][N];

int visited[N][N];

typedef struct node

{

    int x,y;

    int step; // 统计多少步 

} Node;

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

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

// 后续用于移动

// 检查是否可以通行 

int check(Node p)

{

    if(p.x<0 || p.x>=r || p.y<0 || p.y>=c) return 0;

    // 更新判断条件：空地字符为'-'，起点为'S'，终点为'E'

    if(mp[p.x][p.y] == '#') return 0; 

    return 1; // 否则可以通行

} 

int bfs(Node begin, Node end)

{

    // 重置visited数组

    memset(visited, 0, sizeof(visited));

    queue<Node> q; // 初始化队列

    q.push(begin);

    visited[begin.x][begin.y] = 1;

    while(!q.empty()) // 非空 

    {

        Node top = q.front(); // 取队首

        q.pop(); // 出队

        if(top.x == end.x && top.y == end.y)

            return top.step;

        // 尝试四个方向移动

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

        {

            Node newnode;

            newnode.x = top.x + dx[i]; // 移动

            newnode.y = top.y + dy[i]; // 移动 

            if(check(newnode) == 1 && visited[newnode.x][newnode.y] == 0)

            // 可以通行，且没有通行过 

            {

                newnode.step = top.step + 1;

                q.push(newnode);

                visited[newnode.x][newnode.y] = 1; 

            } 

        } 

    } 

    return -1;

}

int main()

{

    cin >> n;

    while(n--)

    {

        cin >> r >> c;

        Node begin, end;

        bool foundStart = false, foundEnd = false;

        // 读取迷宫并查找起点和终点

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

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

            {

                cin >> mp[i][j];

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

                {

                    begin.x = i;

                    begin.y = j;

                    foundStart = true;

                }

                if(mp[i][j] == 'E')

                {

                    end.x = i;

                    end.y = j;

                    foundEnd = true;

                }

            }

        // 确保找到了起点和终点

        if(!foundStart || !foundEnd)

        {

            cout << -1 << endl;

            continue;

        }

        begin.step = 0;

        int cnt = bfs(begin, end);

        cout << cnt << endl;

    }

    return 0;

}