[蓝桥杯2015年第六届真题-穿越雷区] BFS 宽搜最短路

解题思路: 求最短路用bfs 模板题 注意判断符号交替

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int dist[N][N];

char g[N][N];

int bx, by, ex, ey, n;

typedef pair<int, int> PII;

queue<PII> q;

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

int bfs() {

    memset(dist, -1, sizeof dist);

    dist[bx][by] = 0;

    q.push({bx, by});

    while (q.size()) {

        auto t = q.front();

        q.pop();

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

            int tx = t.first + dx[i], ty = t.second + dy[i];

            if (g[tx][ty] == g[t.first][t.second]) continue;

            if (tx > 0 && tx <= n && ty > 0 && ty <= n && dist[tx][ty] == -1) {

                dist[tx][ty] = dist[t.first][t.second] + 1;

                q.push({tx, ty});

                if (tx == ex && ty == ey) return dist[tx][ty];

            }

        }

    }

    return dist[ex][ey];

}

int main(void) {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            cin >> g[i][j];

            if (g[i][j] == 'A') bx = i, by = j;

            if (g[i][j] == 'B') ex = i, ey = j;

        }

    }

    printf("%d\n", bfs());

    return 0;

}