1 条题解

  • 0
    @ 2023-8-31 15:52:47
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int n, m;
    char g[305][305];
    struct Point
    {
        int x, y;
        bool operator==(const Point &a)
        {
            return x == a.x && y == a.y;
        }
    };
    Point w[26][2], e;
    queue<Point> q;
    bool vis[305][305];
    int dis[305][305];
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> m;
        memset(w, -1, sizeof(w));
        memset(dis, -1, sizeof(dis));
        memset(vis, false, sizeof(vis));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                cin >> g[i][j];
                if (g[i][j] == '@')
                {
                    q.push(Point{i, j});
                    vis[i][j] = true;
                    dis[i][j] = 0;
                }
                if ('A' <= g[i][j] && g[i][j] <= 'Z')
                {
                    if (w[g[i][j] - 'A'][0].x == -1)
                    {
                        w[g[i][j] - 'A'][0].x = i;
                        w[g[i][j] - 'A'][0].y = j;
                    }
                    else
                    {
                        w[g[i][j] - 'A'][1].x = i;
                        w[g[i][j] - 'A'][1].y = j;
                    }
                }
                if (g[i][j] == '=')
                {
                    e.x = i;
                    e.y = j;
                }
            }
        }
        while (!vis[e.x][e.y] && !q.empty())
        {
            Point h = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                Point nxt = Point{h.x + dx[i], h.y + dy[i]};
                if (nxt.x < 1 || nxt.x > n || nxt.y < 1 || nxt.y > m)
                    continue;
                if (g[nxt.x][nxt.y] == '#')
                    continue;
                if (vis[nxt.x][nxt.y])
                {
                    continue;
                }
                vis[nxt.x][nxt.y] = true;
                if ('A' <= g[nxt.x][nxt.y] && g[nxt.x][nxt.y] <= 'Z')
                {
                    if (w[g[nxt.x][nxt.y] - 'A'][0] == nxt)
                        nxt = w[g[nxt.x][nxt.y] - 'A'][1];
                    else
                        nxt = w[g[nxt.x][nxt.y] - 'A'][0];
                    if (nxt.x < 1 || nxt.x > n || nxt.y < 1 || nxt.y > m)
                        continue;
                }
                q.push(nxt);
                dis[nxt.x][nxt.y] = dis[h.x][h.y] + 1;
            }
        }
        cout << dis[e.x][e.y] << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    1325
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    5
    已通过
    4
    上传者