简单版bfs解法

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int MAX=105;

int row,col;//定义行，列

char mp[MAX][MAX];

bool vis[MAX][MAX];//标记是否走过

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

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

struct Node

{

    int x,y;

    int step;

};

//检查点能否走

bool check(int x,int y)

{

    if(x<0||x>=row||y<0||y>=col) return false;

    if(mp[x][y]=='#') return false;

    if(vis[x][y]==true) return false;

    return true;

}

//bfs

int bfs(int startX,int startY,int endX,int endY)

{

    queue<Node> q;

    Node start;

    start.x=startX;

    start.y=startY;

    start.step=0;

    q.push(start);

    vis[start.x][start.y]=true;

    while(!q.empty())

    {

        Node now=q.front();

        q.pop();

        if(now.x==endX&&now.y==endY) return now.step;

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

        {

            int nx=now.x+dx[i];

            int ny=now.y+dy[i];

            if(check(nx,ny)==true)

            {

                Node next;

                next.x=nx;

                next.y=ny;

                next.step=now.step+1;

                q.push(next);

                vis[nx][ny]=true;

            }

        }

    }

    return -1;

}

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

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

        cin>>row>>col;

        int sx,sy,ex,ey;

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

        {

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

            {

                cin>>mp[i][j];

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

                {

                    sx=i;

                    sy=j;

                }

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

                {

                    ex=i;

                    ey=j;

                }

            }

        }

        int ans=bfs(sx,sy,ex,ey);

        cout<<ans<<endl;

    }

    return 0;

}