QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381457 | #5514. Maze | stegatxins0# | 8 | 62ms | 27748kb | C++20 | 2.6kb | 2024-04-07 18:05:22 | 2024-07-04 03:33:47 |
Judging History
answer
// {{{
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
using ll = long long;
const int inf = 1073741823;
const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define rep(i, b) for (auto i = 0; i < (b); i++)
#define reps(i, b) for (auto i = 1; i <= (b); i++)
#define maxn 100005
int fx[] = {-1, 1, 0, 0};
int fy[] = {0, 0, -1, 1};
// }}}
int n,m,r,c,x1,Y1,x2,y2;
vector<vector<int>> vis, dis;
bool valid(int x, int y)
{
if(x >= 0 and x < n and y >= 0 and y < m and !vis[x][y]) return true;
else return false;
}
void bfs(int sx, int sy, vector<vector<int>>& grid)
{
vis[sx][sy] = 1;
dis[sx][sy] = 0;
deque<pair<int,int>> q;
q.push_front({sx, sy});
while(!q.empty()) {
pair<int,int> top = q.front();
int x = top.first;
int y = top.second;
q.pop_front();
for(int k=0; k<4; k++) {
int tx = x + fx[k];
int ty = y + fy[k];
if(valid(tx, ty)) {
vis[tx][ty] = 1;
if(grid[tx][ty] == 1) {
dis[tx][ty] = dis[x][y] + 1;
q.push_back({tx, ty});
}
else {
dis[tx][ty] = dis[x][y];
q.push_front({tx, ty});
}
}
}
}
}
int subtask1(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size();
vector<int> v;
for(int j=0; j<m; j++) v.push_back(0);
for(int i=0; i<n; i++) {
vis.push_back(v);
dis.push_back(v);
}
bfs(x1, Y1, grid);
int ans = dis[x2][y2];
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> r >> c >> n;
vector<vector<int>> mat(r, vector<int>(c));
//int x1, Y1, x2, y2;
cin >> x1 >> Y1 >> x2 >> y2;
//printf("%d%d",&x1,&Y1);
//printf("%d%d",&x2,&y2);
--x1, --Y1, --x2, --y2;
//cin >> x1;
rep(i,r){
rep(j,c){
char inp;
cin >> inp;
//scanf("%c",&inp);
if(inp=='#')mat[i][j]=1;
else mat[i][j] = 0;
}
}
//debug(mat);
if(n==1){
n=r, m=c;
cout << subtask1(mat) << "\n";
return 0;
}
cout << "h";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 1ms
memory: 3636kb
input:
31 32 1 25 22 5 3 ################################ ################################ .############################### .############################### ##..###############.############ ###.###############.############ #####.########################## ###.#.########################## ###.##############...
output:
26
result:
ok single line: '26'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
31 32 1 31 5 18 30 ................................ ..........................#..... ................................ .................#.............. ................................ ................................ ....#........................... ................................ ....................
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
31 32 1 7 10 1 32 .#...#.####...#.####..###..####. .#.##.#..#.###.#.#####.#..#..##. .#.#######.########..#.#....#.#. ####.##########.####.#..###...## ####.##....####.####..####.##.## ##.###..#####..#.###..#.##.#.#.# ####.###...##.........###.#.#### .##..##.##.######....##.#####.## ####.#.###.##.#......
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
31 32 1 18 18 1 18 #################.############## ################################ ################################ ################################ ################################ ################################ ###############.################ ################################ #################...
output:
15
result:
ok single line: '15'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1 1000 1 1 597 1 432 ..........................................................#..........................................................................................................................................#................................................................#...................
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 1000 1 1 354 1 826 #############################################################.#########################################################################################################################################################################################################################...
output:
463
result:
ok single line: '463'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1 4 1 1 4 1 3 #...
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
1 45 1 1 8 1 20 #######.####.#####..#####################.###
output:
9
result:
ok single line: '9'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
3 13 1 1 5 2 3 .....##.....# .#....##.##.. ......#......
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 2 1 1 1 1 2 ..
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
1 148 1 1 91 1 89 .####.#.###...#..####..####.###..#...#.##.#####.######.#.#....#...####..##.#.#.##...##...#.##.#.#####.#####...#.#.###.#.#...##...###..#...##..##.###
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2 84 1 1 11 1 62 .#..#.##.#.#.##.#.##.#.#...######.#.###...##.#####....##.##.#..###.###.##...##.#...# .#....##.#.#..#...#....##..###..#.##.#...###.#.#.###...##.#....#...##.#..####.#.###.
output:
20
result:
ok single line: '20'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 59 1 1 6 1 20 #.###.########.###..##.####.###.##.##########.########..#.#
output:
11
result:
ok single line: '11'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
31 32 1 31 5 18 30 ................................ ..#...####.######..##.#.####.##. ..#.#.####.#####.##..######..#.. .##.####.#.#.#...##.##########.. ..#...###.#####...####.#####.##. .#..###....#.#.#.##..###.#..#.#. .#.###..###.###.#####.#.#######. ..#...#.####.########...#..####. ..#..#.##...........
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
31 32 1 17 32 11 7 ................................ .#.##.#..#.###.#######.#.###.##. .#.#######.#########.#.#....#.#. .###.##########.####.#..###.#.#. .######.#..##########.####.##.#. .#.###..######.#.###..#.##.#.#.. .###.###.#.##........######.###. .##.###.##.######....##.#####.#. .#####.###.####.....
output:
2
result:
ok single line: '2'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
31 32 1 7 11 13 25 ................................ .##############################. .##############################. .##############################. .##############################. .##############################. .#########.####.###############. .##############################. .################...
output:
11
result:
ok single line: '11'
Test #17:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
244 245 1 226 133 105 7 .####.##################################################.###.#############.########.#######.#########################################.################.####.#################.######################################.###########.######.#####.######. .####.######.#####.#####.#####...
output:
163
result:
ok single line: '163'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3928kb
input:
1 46212 1 1 39597 1 10273 #########################################.########################.##############################################################################################.##################.########.####################.##########################################.####################...
output:
28589
result:
ok single line: '28589'
Test #19:
score: 0
Accepted
time: 2ms
memory: 4588kb
input:
244 245 1 226 133 105 7 ..................................................#...............................................................................................#........................................................#......................................... .................................
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 3ms
memory: 4368kb
input:
244 245 1 214 117 83 245 .##..#.###.##.#.###.#..#####....#..##.##..##.##.#.###.#.##.####.###.....#.#...###.#.###..##.#.##.####..##..#..##....#.###.##.#########.#.#.##.##.#.####.##.##.##.#.##.##..##.##.#..#.#...##..##..#..#..#..####.#.###.##.#..#.#####....##.##.##.#.##.. #.###.##.#..###...###########...
output:
45
result:
ok single line: '45'
Test #21:
score: 0
Accepted
time: 2ms
memory: 4272kb
input:
244 245 1 15 226 207 34 ########################################################################################################################################################################.############################################################################ ##############################...
output:
340
result:
ok single line: '340'
Test #22:
score: 0
Accepted
time: 2ms
memory: 4088kb
input:
1 60000 1 1 59085 1 9263 .........................................................................................................................................................................................................................................................#............................
output:
496
result:
ok single line: '496'
Test #23:
score: 0
Accepted
time: 2ms
memory: 4004kb
input:
1 60000 1 1 57861 1 18234 ##################.###########.##################.###################################################################.#################.#####.##########################################################################.###########################.#########.##################....
output:
39210
result:
ok single line: '39210'
Test #24:
score: 0
Accepted
time: 3ms
memory: 4332kb
input:
244 245 1 226 133 105 7 ..................................................................................................................................................................................................................................................... ..#...#.#..####..####.......##...
output:
2
result:
ok single line: '2'
Test #25:
score: 0
Accepted
time: 3ms
memory: 4536kb
input:
244 245 1 214 117 83 245 ..................................................................................................................................................................................................................................................... ..###.##.#..###...###########...
output:
8
result:
ok single line: '8'
Test #26:
score: 0
Accepted
time: 2ms
memory: 4524kb
input:
244 245 1 15 226 207 34 ..................................................................................................................................................................................................................................................... .#############################...
output:
44
result:
ok single line: '44'
Test #27:
score: 0
Accepted
time: 2ms
memory: 5016kb
input:
387 387 1 335 36 90 357 ##########.##########.#######.#########.####.##########################.#################.##############################################################.######################.###################.##.###########.#####################.############.##################.#.#########...
output:
384
result:
ok single line: '384'
Test #28:
score: 0
Accepted
time: 3ms
memory: 4112kb
input:
2 30695 1 1 15156 1 6032 #..####.##..##..##.##.##..######.##.#.###.###########...####.#.###.#.###.#..###.#.###....###.#####..#...##.##.######.####.#######.######..#...#.#.##....##.##.#..#.#######.#.####.#.#####.##......###.#.#...#..#####.#.###.#####.############..###.#.#####.#...#.##...#..#.###..##....
output:
4487
result:
ok single line: '4487'
Test #29:
score: 0
Accepted
time: 4ms
memory: 5700kb
input:
387 387 1 55 282 267 35 .......................................................................................................................................................................................................................................................................................
output:
0
result:
ok single line: '0'
Test #30:
score: 0
Accepted
time: 6ms
memory: 5368kb
input:
387 387 1 287 270 56 102 #.#####.###..#..#.##..######...####..####.###..####.....#######.##..##..#.###.#..#..##.##.#...#.#.#.#.####.##...#.##..#.#.#..####.##.##.###......#.####..#####.####..##.#.#.#####..####.####.###.###..#.....#######.###.###.##..#.##..#...###..############.#.###.#..##.##..####.##...
output:
66
result:
ok single line: '66'
Test #31:
score: 0
Accepted
time: 4ms
memory: 4876kb
input:
387 387 1 182 105 119 379 ##########################.######################################################################################################################################################################################################.################################################...
output:
312
result:
ok single line: '312'
Test #32:
score: 0
Accepted
time: 4ms
memory: 5460kb
input:
1 150000 1 1 113832 1 2038 .............................................................................#......................................................................................................................................................................................................
output:
1092
result:
ok single line: '1092'
Test #33:
score: 0
Accepted
time: 2ms
memory: 5404kb
input:
1 150000 1 1 6957 1 130571 ####.##########################################################################.################################################################################.################################################.###############################################################...
output:
122389
result:
ok single line: '122389'
Test #34:
score: 0
Accepted
time: 6ms
memory: 5644kb
input:
387 387 1 55 282 267 35 .......................................................................................................................................................................................................................................................................................
output:
11
result:
ok single line: '11'
Test #35:
score: 0
Accepted
time: 6ms
memory: 5408kb
input:
387 387 1 287 270 56 102 ......................................................................................................................................................................................................................................................................................
output:
35
result:
ok single line: '35'
Test #36:
score: 0
Accepted
time: 4ms
memory: 5428kb
input:
387 387 1 369 107 192 382 .....................................................................................................................................................................................................................................................................................
output:
21
result:
ok single line: '21'
Test #37:
score: 0
Accepted
time: 55ms
memory: 21580kb
input:
1224 1225 1 106 825 1167 186 ##################################.#######.##..##.#.####.############.######.################.###################.#########.###########################.#####.####################.###############################.#######################.#######.########################.###...
output:
1112
result:
ok single line: '1112'
Test #38:
score: 0
Accepted
time: 7ms
memory: 5372kb
input:
16 10623 1 16 1171 14 2438 ###.#....#.##..#.#.#.#.##.#.#..#.###..###.#..#...##..#.###..#...##.####.#......##...#..#..###...#..#####.#..##.#.###.#...#.##..#####.#######.....#.....#######.##.#....#.#...###..##..####.####.#.###.#####.#.##.###...#.....##.###.#.#.......#.###.##.#.###########.##.......##....
output:
185
result:
ok single line: '185'
Test #39:
score: 0
Accepted
time: 0ms
memory: 6120kb
input:
1 184339 1 1 58622 1 95339 .....#.....#.##.#.....#................#.....#.....#.#........#......................##.......#..#.....#....#.....##......#.................#............##.#....#..##......#...#.............#.......##.#............#.#....#....#...#...#..##.#...................#..#....##..#...
output:
5653
result:
ok single line: '5653'
Test #40:
score: 0
Accepted
time: 8ms
memory: 5668kb
input:
185 1158 1 170 697 18 48 #########.########.###.####.##########.################.#.##.#######.##.##.########.#.#############.####..###.##.####.###..###.####.#################.##..#######.#.###..#.#####..#.#.##.#.####.#.###########.####.###################..#####.############.###.#####.###..######..#...
output:
453
result:
ok single line: '453'
Test #41:
score: 0
Accepted
time: 8ms
memory: 6284kb
input:
2 121141 1 1 84070 2 47224 ########.#.######.#.#####.##.###.##.####.#...####..#...#.#####.##.###.#.#######.##.##.######.###.#####.#####.####...#..#####.###########.####...#.########..##..####.###.###.####.###.#.###..####..###.##.####.##.#######.#..######.#.#....###.##.##.###.####...#.#.#.##.##.###.#...
output:
23385
result:
ok single line: '23385'
Test #42:
score: 0
Accepted
time: 27ms
memory: 12180kb
input:
6 123737 1 3 116020 4 86192 ...#..#..#.............#.#.##.##...#..#...#...#...........#..#...#......##......#.#...#..#.##..#####..........#.#.....#.#.####......#....#.....##.##.####...........#.#.##..###.....#.#.#...#.#..#..#.#.#..#..#....#..#.......#...#...#...#.#.##..#..#..##......#..#...#...#.......
output:
1725
result:
ok single line: '1725'
Test #43:
score: 0
Accepted
time: 29ms
memory: 13260kb
input:
5 160357 1 1 41933 1 68874 ##########.###.##.#.#####..#.#####.###..##.#############################.#############.##.#####.##########.##########.###.############..########.#####.#.######.###..####.####.##########.#####.###.##########..#.#######.##.###.#..#.###############.##############.###.###..###...
output:
20843
result:
ok single line: '20843'
Test #44:
score: 0
Accepted
time: 33ms
memory: 23676kb
input:
1224 1225 1 520 1165 390 755 .............................#....................................................................................................................................................................................................................................................
output:
0
result:
ok single line: '0'
Test #45:
score: 0
Accepted
time: 58ms
memory: 21308kb
input:
1224 1225 1 1155 1123 435 159 ###....#.#.##.##.####.##.###.##########.##.####.#.#..##.##..#..####...#..#.....#####....####.###.#####...#..#..#....###.#....#....#.##.#.....##...##.#...##...####.####..#.#####.##..#.##.##.#.###.#..##.##.##..###.##..#.....#############.#####.#.##...##.#.####.#########.#...
output:
276
result:
ok single line: '276'
Test #46:
score: 0
Accepted
time: 48ms
memory: 20788kb
input:
1224 1225 1 533 1130 900 376 ############################################################.###############################.########################.######################################################################.###############################################################.##################...
output:
1015
result:
ok single line: '1015'
Test #47:
score: 0
Accepted
time: 34ms
memory: 27748kb
input:
1 1500000 1 1 32769 1 947728 .................................................................................................................................................#................................................................................................................................
output:
9041
result:
ok single line: '9041'
Test #48:
score: 0
Accepted
time: 27ms
memory: 26744kb
input:
1 1500000 1 1 1314999 1 652665 ##########################################################################################.###################################################.#############################################################################################.################################...
output:
655757
result:
ok single line: '655757'
Test #49:
score: 0
Accepted
time: 62ms
memory: 21528kb
input:
1224 1225 1 969 785 150 464 ...................................................................................................................................................................................................................................................................................
output:
37
result:
ok single line: '37'
Test #50:
score: 0
Accepted
time: 56ms
memory: 21452kb
input:
1224 1225 1 1155 1123 435 159 .................................................................................................................................................................................................................................................................................
output:
49
result:
ok single line: '49'
Test #51:
score: 0
Accepted
time: 43ms
memory: 21332kb
input:
1224 1225 1 533 1130 900 376 ..................................................................................................................................................................................................................................................................................
output:
407
result:
ok single line: '407'
Subtask #2:
score: 0
Wrong Answer
Test #52:
score: 0
Wrong Answer
time: 0ms
memory: 3532kb
input:
3 6 2 2 1 3 3 ...### ..##.. #..###
output:
h
result:
wrong answer 1st lines differ - expected: '0', found: 'h'
Subtask #3:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 0ms
memory: 3540kb
input:
35 60 20 3 60 2 44 .#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####. #.#......#.####..####...#...#......#........####....##.#.### .#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##. .#.#...##..#.##.......#......##......####...##.##..##.#....# #...#.......#..#..#...#.#####.##.###....
output:
h
result:
wrong answer 1st lines differ - expected: '1', found: 'h'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #3:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #7:
0%