32pts求调,悬3关
查看原帖
32pts求调,悬3关
482998
jeffstart楼主2023/9/24 10:10
#include <bits/stdc++.h>
using namespace std;

const int N = 310;
char a[N][N];
typedef pair<int, int> P;
vector<int> vec[26];
map<int, vector<int>> G;
int d[N * N], st[N * N];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, s});
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) {
            continue;
        }
        for (auto e : G[v]) {
            if (st[v] == e) {
                if (d[e] > d[v]) {
                    d[e] = d[v];
                    que.push({d[e], e});
                }
            }
            if (d[e] > d[v] + 1) {
                d[e] = d[v] + 1;
                que.push({d[e], e});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    int sx = 0, sy = 0, gx = 0, gy = 0;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            a[i][j] = s[j - 1];
            if (a[i][j] == '@') {
                sx = i, sy = j;
            }
            if (a[i][j] == '=') {
                gx = i, gy = j;
            }
            if (a[i][j] >= 'A' && a[i][j] <= 'Z') {
                vec[a[i][j] - 'A'].push_back((i - 1) * n + j);
            }
        }
    }
    for (int i = 0; i < 26; i++) {
        if (vec[i].size() == 2) {
            G[vec[i][0]].push_back(vec[i][1]);
            G[vec[i][1]].push_back(vec[i][0]);
            st[vec[i][1]] = vec[i][0];
            st[vec[i][0]] = vec[i][1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j != m) {
                if (a[i][j + 1] != '#') {
                    G[(i - 1) * n + j].push_back((i - 1) * n + j + 1);
                }
            }
            if (j > 1) {
                if (a[i][j - 1] != '#') {
                    G[(i - 1) * n + j].push_back((i - 1) * n + j - 1);
                }
            }
            if (i != n) {
                if (a[i + 1][j] != '#') {
                    G[(i - 1) * n + j].push_back(i * n + j);
                }
            }
            if (i > 1) {
                if (a[i - 1][j] != '#') {
                    G[(i - 1) * n + j].push_back((i - 2) * n + j);
                }
            }
        }
    }
    dijkstra((sx - 1) * n + sy);
    cout << d[(gx - 1) * n + gy] << "\n";
    return 0;
}

有什么结果直接@我,否则我有可能看不到

2023/9/24 10:10
加载中...