QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#649753 | #5514. Maze | liuziao | 0 | 19ms | 31552kb | C++23 | 3.1kb | 2024-10-18 09:53:38 | 2024-10-18 09:53:39 |
Judging History
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%