QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#647739 | #5514. Maze | liuziao# | 0 | 27ms | 47848kb | C++23 | 2.3kb | 2024-10-17 15:31:46 | 2024-10-17 15:31:46 |
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<std::pair<int, 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];
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
std::priority_queue<std::pair<int, int>> q;
dis[s] = 0, q.emplace(0, s);
for (; !q.empty();) {
int u = q.top().second; q.pop();
// std::cerr << (u - 1) / m + 1 << ' ' << (u - 1) % m + 1 << ' ' << dis[u] << '\n';
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w] : G[u]) {
if (u == s && ::s[sx][sy] == '#' && !w) continue;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.emplace(-dis[v], v);
}
}
}
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 (s[i][j] != '.') continue;
if (i < n && s[i + 1][j] == '.') {
G[getid(i, j)].emplace_back(getid(i + 1, j), 0);
}
if (j < m && s[i][j + 1] == '.') {
G[getid(i, j)].emplace_back(getid(i, j + 1), 0);
}
if (i > 1 && s[i - 1][j] == '.') {
G[getid(i, j)].emplace_back(getid(i - 1, j), 0);
}
if (j > 1 && s[i][j - 1] == '.') {
G[getid(i, j)].emplace_back(getid(i, j - 1), 0);
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int x = i; x <= std::min(n, i + k); ++x) {
for (int y = j; y <= std::min(m, j + k); ++y) {
if (std::min(x - i, y - j) <= k - 1) {
G[getid(i, j)].emplace_back(getid(x, y), 1);
G[getid(x, y)].emplace_back(getid(i, j), 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: 7ms
memory: 33548kb
input:
31 32 1 25 22 5 3 ################################ ################################ .############################### .############################### ##..###############.############ ###.###############.############ #####.########################## ###.#.########################## ###.##############...
output:
33
result:
wrong answer 1st lines differ - expected: '26', found: '33'
Subtask #2:
score: 0
Wrong Answer
Test #52:
score: 19
Accepted
time: 4ms
memory: 33376kb
input:
3 6 2 2 1 3 3 ...### ..##.. #..###
output:
0
result:
ok single line: '0'
Test #53:
score: 19
Accepted
time: 10ms
memory: 35288kb
input:
4 24 4 3 4 3 3 ..#...##.#...###...###.# .##.#..##.##.##..#.####. #.......#.#.#...#.#####. ######....######.#...#.#
output:
0
result:
ok single line: '0'
Test #54:
score: 0
Wrong Answer
time: 4ms
memory: 34936kb
input:
2 136 2 1 133 2 45 #############################################.##################.#.#######.##############.#################.##############.##.######.### ####.########.###############.####.###..####.#.###.#################.##..##############.###.############################################
output:
45
result:
wrong answer 1st lines differ - expected: '41', found: '45'
Subtask #3:
score: 0
Wrong Answer
Test #64:
score: 16
Accepted
time: 22ms
memory: 47848kb
input:
35 60 20 3 60 2 44 .#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####. #.#......#.####..####...#...#......#........####....##.#.### .#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##. .#.#...##..#.##.......#......##......####...##.##..##.#....# #...#.......#..#..#...#.#####.##.###....
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Wrong Answer
time: 27ms
memory: 46608kb
input:
63 602 3 10 463 3 402 #.#.#..#..######.#.##.##.#########.###.##.##..#..####.#...#########..###..####.######.###.##.#.....############.####.########.#.########.##.######.###..#####.###..##.#..#..##..##.###..##.###.#######...#.##.##.#.#.##...##...####.###.##.#.#.....#####.##.#..#.##..#...######.#####....
output:
14
result:
wrong answer 1st lines differ - expected: '9', found: '14'
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%