【2021】阿里巴巴编程题（4星）4. 对称飞行器

经典bfs

#include <iostream>
#include <queue>
using namespace std;
const int N = 510;
struct q_item{
    int x,y,d,cnt;  //分别表示  位置、步数、使用对称次数
};
queue<q_item> q;
vector<string> g(1,"");
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int n,m;
int st[N][N];
int bfs(const vector<string>g, int sx, int sy)
{
    //起点入队
    q.push({sx,sy,0,0});
    //出队
    while(q.size())
    {
        q_item & t = q.front();
        q.pop();
        //判断出队元素
        if(g[t.x][t.y]=='E')
        {
            return t.d;
        }
        //四向扩展
        for(int i = 0;i<4;i++)
        {
            int a = t.x+dx[i];
            int b = t.y + dy[i];
            if(a<=0 || a>n || b<=0 || b> m || st[a][b] || g[a][b]=='#')
                continue;
            q.push({a,b,t.d+1,t.cnt});
            st[a][b] = 1;
        }
        //对称扩展
        int a = n+1-t.x;
        int b = m+1-t.y;
        if(a<=0 || a>n || b<=0 || b> m || st[a][b] || t.cnt+1>5 || g[a][b]=='#')
            continue;
        q.push({a,b,t.d+1,t.cnt+1});
        st[a][b] = 1;

    }
    return -1;
}

int main()
{

    cin >> n >> m;
    int sx,sy;
    for(int i = 1;i<=n;i++)
    {
        string s;
        cin >> s;
        s.insert(s.begin(),' ');
        for(int j = 1; j<=m;j++)//寻找起始点
        {
            if(s[j]=='S'){
                sx = i;
                sy = j;
            }
        }
        g.push_back(s);
    }
    cout << bfs(g, sx, sy) << endl;
    return 0;
}