QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649753#5514. Mazeliuziao0 19ms31552kbC++233.1kb2024-10-18 09:53:382024-10-18 09:53:39

Judging History

你现在查看的是最新测评结果

  • [2024-10-18 09:53:39]
  • 评测
  • 测评结果:0
  • 用时:19ms
  • 内存:31552kb
  • [2024-10-18 09:53:38]
  • 提交

answer

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxT = 6e6 + 5, kMaxN = 3e3 + 5;

int n, m, k;
int sx, sy, tx, ty;
std::vector<int> G[kMaxT];
std::string s[kMaxN];

int getid(int x, int y) { return (x - 1) * m + y; }

void dijkstra(int s, int t) {
  static int dis[kMaxT];
  // static bool vis[kMaxT];
  static std::bitset<kMaxT> vis;
  memset(dis, 0x3f, sizeof(dis));
  // memset(vis, 0, sizeof(vis));
  for (int i = 0; i < kMaxT; ++i) vis[i] = 1;
  std::deque<int> q;
  dis[s] = 0, vis[s] = 0, q.emplace_back(s);
  for (int tm = 0; !q.empty(); ++tm) {
    std::vector<int> vec;
    if (vis[t]) return void(std::cout << dis[t] << '\n');
    for (; !q.empty() && dis[q.front()] == tm;) {
      int u = q.front(); q.pop_front();
      vec.emplace_back(u);
      // std::cerr << (u - 1) / m + 1 << ' ' << (u - 1) % m + 1 << ' ' << dis[u] << '\n';
      for (auto v : G[u]) {
        if (dis[v] > dis[u]) {
          dis[v] = dis[u], vis[v] = 0;
          q.emplace_front(v);
        }
      }
    }
    for (auto u : vec) {
      int x = (u - 1) / m + 1, y = (u - 1) % m + 1;
      for (int i = std::max(x - k, 1); i <= std::min(x + k, n); ++i) {
        // for (int j = std::max(y - k, 1); j <= std::min(y + k, m); ++j) {
        for (int v = vis._Find_next((i - 1) * m + std::max(y - k, 1) - 1);
             v <= (i - 1) * m + std::min(y + k, m); v = vis._Find_next(v)) {
          int j = v - (i - 1) * m;
          if (std::min(abs(i - x), abs(j - y)) <= k - 1) {
            dis[getid(i, j)] = dis[u] + 1, vis[getid(i, j)] = 0;
            q.emplace_back(getid(i, j));
          }
        }
      }
    }
  }
  std::cout << dis[t] << '\n';
}

void dickdreamer() {
  std::cin >> n >> m >> k >> sx >> sy >> tx >> ty;
  for (int i = 1; i <= n; ++i) {
    std::cin >> s[i];
    s[i] = " " + s[i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (i < n && s[i + 1][j] == '.') {
        G[getid(i, j)].emplace_back(getid(i + 1, j));
      }
      if (j < m && s[i][j + 1] == '.') {
        G[getid(i, j)].emplace_back(getid(i, j + 1));
      }
      if (i > 1 && s[i - 1][j] == '.') {
        G[getid(i, j)].emplace_back(getid(i - 1, j));
      }
      if (j > 1 && s[i][j - 1] == '.') {
        G[getid(i, j)].emplace_back(getid(i, j - 1));
      }
    }
  }
  // for (int i = 1; i <= n; ++i) {
  //   for (int j = 1; j <= m; ++j) {
  //     for (int x = std::max(i - k, 1); x <= std::min(n, i + k); ++x) {
  //       for (int y = std::max(j - k, 1); y <= std::min(m, j + k); ++y) {
  //         if (std::min(abs(x - i), abs(y - j)) <= k - 1) {
  //           G[getid(i, j)].emplace_back(getid(x, y), 1);
  //         }
  //       }
  //     }
  //   }
  // }
  dijkstra(getid(sx, sy), getid(tx, ty));
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 31552kb

input:

31 32 1
25 22
5 3
################################
################################
.###############################
.###############################
##..###############.############
###.###############.############
#####.##########################
###.#.##########################
###.##############...

output:

1061109567

result:

wrong answer 1st lines differ - expected: '26', found: '1061109567'

Subtask #2:

score: 0
Wrong Answer

Test #52:

score: 0
Wrong Answer
time: 12ms
memory: 31180kb

input:

3 6 2
2 1
3 3
...###
..##..
#..###

output:

1061109567

result:

wrong answer 1st lines differ - expected: '0', found: '1061109567'

Subtask #3:

score: 0
Wrong Answer

Test #64:

score: 0
Wrong Answer
time: 19ms
memory: 28836kb

input:

35 60 20
3 60
2 44
.#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####.
#.#......#.####..####...#...#......#........####....##.#.###
.#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##.
.#.#...##..#.##.......#......##......####...##.##..##.#....#
#...#.......#..#..#...#.#####.##.###....

output:

1061109567

result:

wrong answer 1st lines differ - expected: '1', found: '1061109567'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%