穿越雷区 BFS实现

解题思路:
       BFS实现穿越雷区最短路径，主要是地图的输入，以及起始、终点的坐标计算，然后应用模板实现。
注意事项:
       地图的有效输入，注意：空格
参考代码:

//穿越雷区  BFS搜索

#include <bits/stdc++.h>

using namespace std;

const int N=100;

char mp[N][N];

int vis[N][N];

int n;

int sx,sy,fx,fy;

struct node  //队列结点

{

    int x;  //坐标

    int y;

    int step;//遍历的层数

    char power;  //能量符号

};

queue <struct node> q;

int dx[]={0,1,0,-1};  //坐标偏移量

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

void bfs()

{

    struct node k,t;

    q.push({sx,sy,0,'A'});//起始坐标(sx,sy)结点入队

    vis[sx][sy]=1;  //标记(sx,sy)已被访问

    while(!q.empty())//队列非空，循环出队、入队

    {

        k=q.front();//获取队头结点

        q.pop();//出队

        if (k.x==fx&&k.y==fy)//若到达终点，则输出路径长度

        {

                cout<<k.step<<endl;

                break;

        }

        for (int i=0;i<4;i++)//非终点，则继续4个方向广度搜索

        {

            int nx=k.x+dx[i];//新坐标

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

            if (nx>=0&&nx<=n&&ny>=0&&ny<=n&&mp[nx][ny]!=k.power&&!vis[nx][ny]) 

            {//新坐标合法，且未被访问，且可通行

                vis[nx][ny]=1;//标记已被访问

                t.x=nx;

                t.y=ny;

                t.step=k.step+1;

                t.power=mp[nx][ny];

                q.push(t);//新结点入队

            }

        }

    }

}

int main()

{

    cin>>n;

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

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

    {

        cin>>mp[i][j];

        if (mp[i][j]=='A') sx=i,sy=j;

        if (mp[i][j]=='B') fx=i,fy=j;

    } 

    bfs();

    return 0;

}