BFS

自己写的

#include<bits/stdc++.h>
using namespace std;
int t, r, c;
char a[210][210];
int startx, starty, endx, endy;
bool vis[210][210];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int ans = 0x3f3f3f3f;
struct node {
    int x;
    int y;
    int foot;
    node() {
        x = 0; y = 0; foot = 0;
    }
    node(int a, int b, int c) {
        x = a; y = b; foot = c;
    }

};
void bfs(int x, int y,int foot) {
    queue<node> q;
    q.push(node(x,y,foot));
    vis[x][y] = true;
    while (!q.empty()) {
        node now;
        now = q.front();
        if (now.x == endx && now.y == endy) {
            ans = now.foot;
            return;
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = now.x + dx[i];
            int yy = now.y + dy[i];
            if (xx >= 0 && xx < r && yy >= 0 && yy <c && !vis[xx][yy] && a[xx][yy] != '#') {
                if (xx == endx && yy == endy) {
                    ans = now.foot + 1;
                    return;
                }
                q.push(node(xx, yy, now.foot + 1));
                vis[xx][yy] = true;

            }

        }

    }
}
bool flag1 = false;
bool flag2 = false;
int main()
{
    cin >> t;
    while (t--) {
        memset(a, 0, sizeof(a));
        memset(vis, false, sizeof(vis));
        ans = 0x3f3f3f3f;
        flag1 = false;
        flag2 = false;
        cin >> r >> c;
        for (int i = 0; i < r; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (a[i][j] == 'S') {
                    startx = i;
                    starty = j;
                    flag1 = true;
                }
                if (a[i][j] == 'E') {
                    endx = i;
                    endy = j;
                    flag2 = true;
                }
                if (flag1 == true && flag2 == true)
                    break;
            }
            if (flag1 == true && flag2 == true)
                break;
        }

        bfs(startx, starty,0);
        if (ans == 0x3f3f3f3f)
            cout << "oop!" << endl;
        else cout << ans << endl;
    }

    return 0;
}

y总写的

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 210;
int n, m;
char g[N][N];
int dist[N][N];
int bfs(PII start, PII end) {
    queue<PII> q;
    memset(dist, -1, sizeof(dist));

    dist[start.x][start.y] = 0;
    q.push(start);
    int dx[4] = { -1,0,1,0 };
    int dy[4] = { 0,1,0,-1 };

    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i];
            int y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m)continue;
            if (g[x][y] == '#')continue;
            if (dist[x][y] != -1)continue;

            dist[x][y] = dist[t.x][t.y] + 1;

            if (end == make_pair(x, y))
                return dist[x][y];
            q.push({ x,y });
        }
    }
    return -1;
}
int main()
{
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            cin >> g[i];
        PII start, end;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'S')
                    start = { i,j };
                else if (g[i][j] == 'E')
                    end = { i,j };
            }
        }
        int distance = bfs(start, end);
        if (distance == -1)puts("oop!");
        else printf("%d\n", distance);
    }

    return 0;
}