CE
  • 板块学术版
  • 楼主Dry_ice
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/8/28 22:31
  • 上次更新2023/11/4 08:41:06
查看原帖
CE
214696
Dry_ice楼主2021/8/28 22:31

帮忙看看这个 ump 怎么错了。CE

#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <stdio.h>
#include <vector>
#include <utility>
#include <unordered_map>
#include <queue>
using namespace std;
const int N = (int)1e6 + 5, inf = 0x3f3f3f3f,
            d[2][4] = {{0, 1, 0, -1}, {-1, 0, 1, 0}};
int m, n, k; char str[N];
vector<vector<char> > g;
unordered_map<pair<int, int>, int> dis;
queue<pair<int, int> > Q; pair<int, int> S, T;
inline bool check(pair<int, int> pr) {
    return pr.first < 1 || pr.first > m
            || pr.second < 1 || pr.second > n
            || g[pr.first][pr.second] == '@';
}
inline void Bfs() {
    Q.push(S); dis[S] = 0;
    for (pair<int, int> cur, temp; !Q.empty(); ) {
        cur = Q.front(); Q.pop();
        if (cur == T) {
            printf("%d\n", dis[cur]);
            return;
        }
        for (int i = 0; i < 4; ++i)
            for (int j = 1; j <= k; ++j) {
                temp = make_pair(cur.first + d[0][i] * j, cur.second + d[1][i] * j);
                if (check(temp)) break;
                if (dis[cur] + 1 > dis[temp]) break;
                if (dis[cur] + 1 < dis[temp]) {
                    dis[temp] = dis[cur] + 1;
                    Q.push(temp);
                }
            }
    }
    puts("-1");
}
int main(void) {
    scanf("%d %d %d %d %d %d %d", &m, &n, &k, &S.first, &S.second, &T.first, &T.second);
    g.assign(m + 1, vector<char> (n + 1));
    for (int i = 1; i <= m; ++i) {
        scanf("%s", str + 1);
        for (int j = 1; str[j] != '\0'; ++j) {
            g[i][j] = str[j];
            dis[make_pair(i, j)] = inf;
        }
    }
    Bfs();
    return 0;
}
2021/8/28 22:31
加载中...