QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#79771 | #5514. Maze | namelessgugugu | 16 | 102ms | 51096kb | C++14 | 4.4kb | 2023-02-20 21:24:32 | 2023-02-20 21:24:34 |
Judging History
answer
#include <algorithm>
#include <cstdio>
#include <cstring>
#define FILEIO(filename) (freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout))
typedef long long ll;
typedef unsigned long long ull;
const int N = 6000005;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int r, c, n;
char s[N];
int col[N];
inline bool inmap(int x, int y)
{
return x >= 0 && x < r && y >= 0 && y < c;
}
inline int getid(int x, int y)
{
return x * c + y;
}
inline void getpos(int id, int &x, int &y)
{
x = id / c, y = id % c;
return;
}
inline bool reach(int x1, int y1, int x2, int y2)
{
int v1 = std::abs(x1 - x2), v2 = std::abs(y1 - y2);
return v1 <= n && v2 <= n && (v1 < n || v2 < n);
}
inline bool reachid(int id1, int id2)
{
int x1, y1, x2, y2;
getpos(id1, x1, y1), getpos(id2, x2, y2);
return reach(x1, y1, x2, y2);
}
int st, ed;
struct DSU
{
int fa[N];
inline void init(int l)
{
for (int i = 0; i < l; ++i)
fa[i] = i;
return;
}
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y)
{
fa[find(x)] = find(y);
return;
}
} Dr, Dc;
inline void del(int id)
{
int x, y;
getpos(id, x, y);
Dr.merge(id, y == c ? r * c : id + 1);
Dc.merge(id, x == r ? r * c : id + c);
return;
}
int dis[N];
int stk[N], top;
int tmp[N], ttop;
int main(void)
{
scanf("%d%d%d", &r, &c, &n);
{
int x, y;
scanf("%d%d", &x, &y);
st = getid(x - 1, y - 1);
scanf("%d%d", &x, &y);
ed = getid(x - 1, y - 1);
}
for (int i = 0; i < r;++i)
{
scanf("%s", s);
for (int j = 0; j < c;++j)
col[getid(i, j)] = s[j] == '#';
}
Dr.init(r * c + 1), Dc.init(r * c + 1);
memset(dis, 0x3f, sizeof(dis)), dis[st] = 0;
stk[++top] = st;
while(1)
{
for (int i = 1;i <= top;++i)
{
int id = stk[i], x, y;
if(id == ed)
return printf("%d\n", dis[id]), 0;
getpos(id, x, y);
del(id);
for (int o = 0; o < 4; ++o)
{
int nx = x + dx[o], ny = y + dy[o];
if(!inmap(nx, ny))
continue;
int yid = getid(nx, ny);
if(!col[yid] && dis[yid] > dis[id])
dis[yid] = dis[id], stk[++top] = yid;
}
}
memcpy(tmp, stk, sizeof(int) * (top + 5)), ttop = top, top = 0;
for (int i = 1; i <= ttop;++i)
{
int id = tmp[i], x, y;
if(reachid(id, ed))
return printf("%d\n", dis[id] + 1), 0;
getpos(id, x, y);
int rl = std::max(0, x - n), rr = std::min(r - 1, x + n);
int cl = std::max(0, y - n), cr = std::min(c - 1, y + n);
int sp = 0, ep = 0;
sp = getid(rl, cl + (!reach(rl, cl, x, y))), ep = getid(rl, cr - (!reach(rl, cr, x, y)));
for (int u = Dr.find(sp); u <= ep;u = Dr.find(u))
// for (int u = sp; u <= ep;++u)
if(dis[u] > dis[id] + 1)
dis[stk[++top] = u] = dis[id] + 1, del(u);
// , printf("a %d %d\n", id, u);
sp = getid(rr, cl + (!reach(rr, cl, x, y))), ep = getid(rr, cr - (!reach(rr, cr, x, y)));
for (int u = Dr.find(sp); u <= ep; u = Dr.find(u))
// for (int u = sp; u <= ep; ++u)
if (dis[u] > dis[id] + 1)
dis[stk[++top] = u] = dis[id] + 1, del(u);
// , printf("b %d %d\n", id, u);
sp = getid(rl + (!reach(rl, cl, x, y)), cl), ep = getid(rr - (!reach(rr, cl, x, y)), cl);
for (int u = Dc.find(sp); u <= ep; u = Dc.find(u))
// for (int u = sp; u <= ep; u += c)
if (dis[u] > dis[id] + 1)
dis[stk[++top] = u] = dis[id] + 1, del(u);
// , printf("c %d %d\n", id, u);
sp = getid(rl + (!reach(rl, cr, x, y)), cr), ep = getid(rr - (!reach(rr, cr, x, y)), cr);
for (int u = Dc.find(sp); u <= ep; u = Dc.find(u))
// for (int u = sp; u <= ep; u += c)
if (dis[u] > dis[id] + 1)
dis[stk[++top] = u] = dis[id] + 1, del(u);
// , printf("d %d %d\n", id, u);
}
}
puts("-1");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 34372kb
input:
31 32 1 25 22 5 3 ################################ ################################ .############################### .############################### ##..###############.############ ###.###############.############ #####.########################## ###.#.########################## ###.##############...
output:
7
result:
wrong answer 1st lines differ - expected: '26', found: '7'
Subtask #2:
score: 0
Wrong Answer
Test #52:
score: 19
Accepted
time: 4ms
memory: 31756kb
input:
3 6 2 2 1 3 3 ...### ..##.. #..###
output:
0
result:
ok single line: '0'
Test #53:
score: 0
Accepted
time: 4ms
memory: 31356kb
input:
4 24 4 3 4 3 3 ..#...##.#...###...###.# .##.#..##.##.##..#.####. #.......#.#.#...#.#####. ######....######.#...#.#
output:
0
result:
ok single line: '0'
Test #54:
score: -19
Wrong Answer
time: 1ms
memory: 31396kb
input:
2 136 2 1 133 2 45 #############################################.##################.#.#######.##############.#################.##############.##.######.### ####.########.###############.####.###..####.#.###.#################.##..##############.###.############################################
output:
21
result:
wrong answer 1st lines differ - expected: '41', found: '21'
Subtask #3:
score: 16
Accepted
Test #64:
score: 16
Accepted
time: 4ms
memory: 33048kb
input:
35 60 20 3 60 2 44 .#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####. #.#......#.####..####...#...#......#........####....##.#.### .#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##. .#.#...##..#.##.......#......##......####...##.##..##.#....# #...#.......#..#..#...#.#####.##.###....
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Accepted
time: 4ms
memory: 31240kb
input:
63 602 3 10 463 3 402 #.#.#..#..######.#.##.##.#########.###.##.##..#..####.#...#########..###..####.######.###.##.#.....############.####.########.#.########.##.######.###..#####.###..##.#..#..##..##.###..##.###.#######...#.##.##.#.#.##...##...####.###.##.#.#.....#####.##.#..#.##..#...######.#####....
output:
9
result:
ok single line: '9'
Test #66:
score: 0
Accepted
time: 11ms
memory: 34260kb
input:
45 1194 5 4 632 37 206 ...#..#............#..........#..##....##......#...##..#..#.............#...#...........##....#.........#.#.##..........#......#..........#.....#...........#........#.#.................#................#..........##.......................#.....#..........#........#........#......
output:
0
result:
ok single line: '0'
Test #67:
score: 0
Accepted
time: 3ms
memory: 33540kb
input:
244 245 244 28 168 222 200 ...#...................................................................................................................................................................#..............................................................#.............. ..............................
output:
0
result:
ok single line: '0'
Test #68:
score: 0
Accepted
time: 3ms
memory: 34236kb
input:
244 245 244 175 140 70 11 ##.##....###.###..######..###.#.#####.##..#.#####.#.###.###.....#....###.#####.##..#.###.####.#..##.####...#.#####.###.##..#######.##.##...#..####.#...#####.##.###.#....##..####.###.#.#####..#.#.##.###.#..#.##.####..#.#.#...#######.######.##.#.. #..#..##.####.###.###..........
output:
1
result:
ok single line: '1'
Test #69:
score: 0
Accepted
time: 10ms
memory: 31292kb
input:
244 245 244 241 52 100 202 #######.###################################################################################################################################################################.######################################################################### ###########################...
output:
1
result:
ok single line: '1'
Test #70:
score: 0
Accepted
time: 11ms
memory: 31392kb
input:
62 967 62 41 1 29 386 ####.######.####.#####...##.##..##.####..######.##...######....#.#..#...#.#.###.##.###...######..#.#.####.###.##.###.#...###..##..####.####.#.#...###..#.#..#..###.....#####.##..##.####..##......#.####.##.#...##..###.#....#..##.###.#..#####.#..#.#.#.##..#..#.#..##.##.####...#.#....
output:
6
result:
ok single line: '6'
Test #71:
score: 0
Accepted
time: 8ms
memory: 32364kb
input:
202 595 58 71 324 182 516 ..#.###....#.##......#............#...#.###....................#....#....#...#.##.........#.....#....#.#.......###.#........#####..#.......###......#......#.......#...##..........#.#.....#.#.................#.#...#..#.#.......#.#.##...#.#..#......#.....#.......#.#..#..#.......
output:
0
result:
ok single line: '0'
Test #72:
score: 0
Accepted
time: 5ms
memory: 32492kb
input:
387 387 387 100 184 358 250 ................#...........................................................................................................................................#......................................................................................................................
output:
0
result:
ok single line: '0'
Test #73:
score: 0
Accepted
time: 2ms
memory: 32364kb
input:
387 387 387 133 20 329 125 #..##.##..###.##.##..######..#####.#.#####..#####.####.#....##.#.#.#.#.##.##..##.###....#.#..#.#.##...###########..##..#.##..##.######.##.#.#####.###.##.#....#..##.##.##.#####..#.##.##.####..#.###.##.##.#.#....###...#.#.###.##..####..##.##.#.#.#.#.###....#.###.#.#..#.###.#...
output:
1
result:
ok single line: '1'
Test #74:
score: 0
Accepted
time: 3ms
memory: 33688kb
input:
387 387 387 201 41 238 340 ###########################################################################.#####################################################################################################################################################################################################...
output:
1
result:
ok single line: '1'
Test #75:
score: 0
Accepted
time: 20ms
memory: 35260kb
input:
601 723 26 258 272 578 200 #.#.....#..#.##.##.##.......#.......#...#..#.....##...##.##..###.....#.....#.#.#....###...#.#....#...##..#..#.####...#..#..#.......#..##.....###...#.#.#....#....####..###.#.##..##....##.....##.#..#.##.#.#....#......#...##.....##.......#..#.#...#..#..##...#...#....####.##.#...
output:
0
result:
ok single line: '0'
Test #76:
score: 0
Accepted
time: 51ms
memory: 46356kb
input:
103 12319 67 96 7020 42 1423 ..##.###......#...#...#.........#........#....#..#...##.......#..###......###...#...##..#.##.##......##..#....#..............#.#......#.#...#...#..#..##.#..#....#.........###...#.....#..#..###...#.......#..#...##...#..####.##.#.##..##...#..#..####...#.......#.#....#..#.#...
output:
0
result:
ok single line: '0'
Test #77:
score: 0
Accepted
time: 102ms
memory: 51096kb
input:
1224 1225 1224 582 110 326 1104 ..................................................................................#...........................................................................................................................................................#................................
output:
0
result:
ok single line: '0'
Test #78:
score: 0
Accepted
time: 8ms
memory: 45500kb
input:
1224 1225 1224 1024 851 437 463 ##..#.###.####..##..#...#.#...##.#.#.########.#.#####..##..##.###..##..##..##.#...#.##.##.#####..###########.#.##...#.###########.####..####...#......##...###..#.#.####.#####.#.####.####.##..#.######..#.#.##.#.#.#.####....#...###.##...#..#..#####..#.#####.#...##.##......
output:
1
result:
ok single line: '1'
Test #79:
score: 0
Accepted
time: 4ms
memory: 45236kb
input:
1224 1225 1224 188 85 758 1157 #####.##.########################################################################################################################################################.###############################################################.###########################################...
output:
1
result:
ok single line: '1'
Test #80:
score: 0
Accepted
time: 59ms
memory: 49112kb
input:
72 20833 72 41 567 6 17116 ##.....##.##..#..###....###.#..##..#.#...#......#.#..###.#..#.#.#..##..#.##.......#...#.###..##.#.#..#....#....##..........#..#...##...#........#..#.#.##.###.#.###....###.#....#.#...#....#.##..#.#.##.#######.#...##....#.#.......##..#..#...##.##.........#..#....#..###.##......
output:
0
result:
ok single line: '0'
Test #81:
score: 0
Accepted
time: 46ms
memory: 48828kb
input:
114 13157 114 100 43 54 9728 .....#.....##.##....##.#..###.###.#..#.#...#....#.##.....#..#.#.###................###...#..#..#.##.#...#..#.##........#...#.#..##...#..###..##.#.....#.#.....#.....##.....#.##..#.#....#..#.##..#..##..#.###.##...#.#.#.#..##...#...#...#.##.##.#.#....#..#.#.........#....##....
output:
0
result:
ok single line: '0'
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%