bfs找最短路

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 110;

typedef pair<int,int> PII;

int n;
char g[N][N];
int f[N][N];
bool st[N][N];
int dx[4] ={-1,0,1,0}, dy[4] = {0,1,0,-1};

int ax,ay,bx,by;

void bfs(int x,int y)
{
    f[x][y] = 0;
    st[x][y] = true;
    queue<PII> q;
    q.push({x,y});
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0;i < 4;i ++)
        {
            int a = t.first + dx[i],b = t.second + dy[i];
            if(a < 0 || a >= n || b <0 || b >= n || st[a][b] || g[a][b] == g[t.first][t.second]) continue;
            f[a][b] = min(f[a][b],f[t.first][t.second] + 1);
            q.push({a,b});
            st[a][b] = true;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ )
        for(int j = 0;j < n;j ++ ){
            cin >> g[i][j];
            if(g[i][j] == 'A') ax = i,ay = j;
            if(g[i][j] == 'B') bx = i,by = j;
        }


    memset(f,0x3f,sizeof f);
    bfs(ax,ay);

    if(f[bx][by] == 0x3f3f3f3f) cout << -1;
    else cout << f[bx][by];

    return 0;
}