QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#504694 | #9108. Zayin and Obstacles | untitledtwo# | AC ✓ | 218ms | 12816kb | C++20 | 2.1kb | 2024-08-04 14:55:31 | 2024-08-04 14:55:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;
int n, m;
int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {0, 0, 0, 0, 1, -1};
int dz[6] = {1, -1, 0, 0, 0, 0};
struct Node{
int x, y, z;
};
queue<Node> que;
int dist[105][105][105], s[105][105][105];
int check(Node q) {
int x = q.x, y = q.y, z = q.z;
if (x < 1 || x > n || y < 1 || y > n || z < 1 || z > n) return 0;
if (s[x][y][z] != 0) return 0;
return 1;
}
void solve() {
for (int i = 1; i <= n ; ++ i)
for (int j = 1; j <= n ; ++ j)
for (int k = 1; k <= n ; ++ k)
s[i][j][k] += s[i - 1][j][k];
for (int i = 1; i <= n ; ++ i)
for (int j = 1; j <= n ; ++ j)
for (int k = 1; k <= n ; ++ k)
s[i][j][k] += s[i][j - 1][k];
for (int i = 1; i <= n ; ++ i)
for (int j = 1; j <= n ; ++ j)
for (int k = 1; k <= n ; ++ k)
s[i][j][k] += s[i][j][k - 1];
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
int Case;
scanf("%d", &Case);
while (Case --) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n ; ++ i)
for (int j = 1; j <= n ; ++ j)
for (int k = 1; k <= n ; ++ k) s[i][j][k] = 0, dist[i][j][k] = INF;
for (int i = 1; i <= m ; ++ i) {
int l1, l2, l3, r1, r2, r3;
scanf("%d%d%d%d%d%d", &l1, &l2, &l3, &r1, &r2, &r3);
++ s[l1][l2][l3];
-- s[r1 + 1][l2][l3];
-- s[l1][r2 + 1][l3];
-- s[l1][l2][r3 + 1];
++ s[r1 + 1][r2 + 1][l3];
++ s[l1][r2 + 1][r3 + 1];
++ s[r1 + 1][l2][r3 + 1];
-- s[r1 + 1][r2 + 1][r3 + 1];
}
solve();
int X, Y, Z;
scanf("%d%d%d", &X, &Y, &Z);
que.push((Node){X, Y, Z}), dist[X][Y][Z] = 0;
while (!que.empty()) {
Node q = que.front(); que.pop();
for (int i = 0; i < 6 ; ++ i) {
Node p = (Node){q.x + dx[i], q.y + dy[i], q.z + dz[i]};
if (check(p) && dist[p.x][p.y][p.z] == INF)
dist[p.x][p.y][p.z] = dist[q.x][q.y][q.z] + 1, que.push(p);
}
}
scanf("%d%d%d", &X, &Y, &Z);
if (dist[X][Y][Z] == INF) printf("-1\n");
else printf("%d\n", dist[X][Y][Z]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5836kb
input:
3 3 0 1 1 1 3 3 3 3 1 2 1 1 2 3 3 1 1 1 3 3 3 3 3 2 1 1 2 2 3 1 1 2 2 3 2 1 2 2 3 3 2 1 1 1 1 1 3
output:
6 -1 14
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 18ms
memory: 12588kb
input:
5 19 27 2 1 1 2 18 19 4 2 1 4 19 19 6 1 1 6 18 19 8 2 1 8 19 19 10 1 1 10 18 19 12 2 1 12 19 19 14 1 1 14 18 19 16 2 1 16 19 19 18 1 1 18 18 19 1 1 2 18 19 2 2 1 4 19 19 4 1 1 6 18 19 6 2 1 8 19 19 8 1 1 10 18 19 10 2 1 12 19 19 12 1 1 14 18 19 14 2 1 16 19 19 16 1 1 18 18 19 18 1 2 2 19 19 2 1 2 4 ...
output:
1998 15998 53998 127998 249998
result:
ok 5 lines
Test #3:
score: 0
Accepted
time: 52ms
memory: 12584kb
input:
5 99 147 2 1 1 2 98 99 4 2 1 4 99 99 6 1 1 6 98 99 8 2 1 8 99 99 10 1 1 10 98 99 12 2 1 12 99 99 14 1 1 14 98 99 16 2 1 16 99 99 18 1 1 18 98 99 20 2 1 20 99 99 22 1 1 22 98 99 24 2 1 24 99 99 26 1 1 26 98 99 28 2 1 28 99 99 30 1 1 30 98 99 32 2 1 32 99 99 34 1 1 34 98 99 36 2 1 36 99 99 38 1 1 38 9...
output:
132878 2596 227782 37198 90672
result:
ok 5 lines
Test #4:
score: 0
Accepted
time: 19ms
memory: 12816kb
input:
5 99 1000 2 1 1 2 98 99 4 2 1 4 99 99 6 1 1 6 98 99 8 2 1 8 99 99 10 1 1 10 98 99 12 2 1 12 99 99 14 1 1 14 98 99 16 2 1 16 99 99 18 1 1 18 98 99 20 2 1 20 99 99 22 1 1 22 98 99 24 2 1 24 99 99 26 1 1 26 98 99 28 2 1 28 99 99 30 1 1 30 98 99 32 2 1 32 99 99 34 1 1 34 98 99 36 2 1 36 99 99 38 1 1 38 ...
output:
4998 4998 4998 4998 4998
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 36ms
memory: 12512kb
input:
5 19 1000 2 1 1 2 18 19 4 2 1 4 19 19 6 1 1 6 18 19 8 2 1 8 19 19 10 1 1 10 18 19 12 2 1 12 19 19 14 1 1 14 18 19 16 2 1 16 19 19 18 1 1 18 18 19 4 13 10 4 19 12 6 5 5 6 6 18 6 16 4 6 18 11 8 6 10 8 17 19 14 10 7 14 17 12 2 4 4 2 5 15 4 5 10 4 7 17 12 1 2 12 2 9 12 8 10 12 18 15 16 19 2 16 19 8 8 1 ...
output:
-1 798 1906 3198 4998
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 218ms
memory: 12784kb
input:
5 100 0 92 81 37 11 85 14 100 0 16 48 91 61 65 58 100 0 87 25 52 83 7 45 100 0 80 95 16 62 5 80 100 0 33 33 50 48 82 3
output:
108 95 29 172 111
result:
ok 5 lines