QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#365005 | #5514. Maze | ksu_# | 0 | 11ms | 4352kb | C++14 | 2.2kb | 2024-03-24 17:59:30 | 2024-07-04 03:31:09 |
Judging History
answer
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef int ll;
#define endl '\n'
typedef pair<ll, pair<ll, ll>> pll;
priority_queue<pll, vector<pll>, greater<pll>> q;
ll n, r, c;
void check(int x, int y, int d, vector<vector<ll>> &dist, vector<string> &a){
if(x >= 1 && y >= 1 && x <= r && y <= c && d < dist[x][y] && a[x][y] == '.'){
dist[x][y] = d;
q.push({d, {x, y}});
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> r >> c >> n;
ll s1, s2, f1, f2;
cin >> s1 >> s2 >> f1 >> f2;
vector<string> a(r + 1);
for(int i = 1; i <= r; i++){
cin >> a[i];
a[i] = "#" + a[i];
}
q.push({0, {s1, s2}});
vector<vector<bool>> used(r + 1, vector<bool> (c + 1));
vector<vector<ll>> dist(r + 1, vector<ll> (c + 1, 1e9));
dist[s1][s2] = 0;
while(!q.empty()){
auto v = q.top();
q.pop();
int x = v.second.first, y = v.second.second;
if(used[x][y])
continue;
if(x == f1 && y == f2)
break;
used[x][y] = 1;
check(x - 1, y, v.first, dist, a);
check(x + 1, y, v.first, dist, a);
check(x, y - 1, v.first, dist, a);
check(x, y + 1, v.first, dist, a);
if(v.first == 10)
continue;
for(int x2 = max(1, x - n); x2 <= min(r, x + n); x2++){
for(int y2 = max(1, y - n); y2 <= min(c, y + n); y2++){
if(abs(x2 - x) < n || abs(y - y2) < n){
if(v.first + 1 < dist[x2][y2]){
dist[x2][y2] = v.first + 1;
q.push({v.first + 1, {x2, y2}});
}
}
}
}
}
cout << dist[f1][f2] << endl;
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: 3612kb
input:
31 32 1 25 22 5 3 ################################ ################################ .############################### .############################### ##..###############.############ ###.###############.############ #####.########################## ###.#.########################## ###.##############...
output:
1000000000
result:
wrong answer 1st lines differ - expected: '26', found: '1000000000'
Subtask #2:
score: 0
Wrong Answer
Test #52:
score: 19
Accepted
time: 0ms
memory: 3780kb
input:
3 6 2 2 1 3 3 ...### ..##.. #..###
output:
0
result:
ok single line: '0'
Test #53:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 24 4 3 4 3 3 ..#...##.#...###...###.# .##.#..##.##.##..#.####. #.......#.#.#...#.#####. ######....######.#...#.#
output:
0
result:
ok single line: '0'
Test #54:
score: -19
Wrong Answer
time: 0ms
memory: 3812kb
input:
2 136 2 1 133 2 45 #############################################.##################.#.#######.##############.#################.##############.##.######.### ####.########.###############.####.###..####.#.###.#################.##..##############.###.############################################
output:
1000000000
result:
wrong answer 1st lines differ - expected: '41', found: '1000000000'
Subtask #3:
score: 0
Time Limit Exceeded
Test #64:
score: 16
Accepted
time: 0ms
memory: 3596kb
input:
35 60 20 3 60 2 44 .#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####. #.#......#.####..####...#...#......#........####....##.#.### .#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##. .#.#...##..#.##.......#......##......####...##.##..##.#....# #...#.......#..#..#...#.#####.##.###....
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
63 602 3 10 463 3 402 #.#.#..#..######.#.##.##.#########.###.##.##..#..####.#...#########..###..####.######.###.##.#.....############.####.########.#.########.##.######.###..#####.###..##.#..#..##..##.###..##.###.#######...#.##.##.#.#.##...##...####.###.##.#.#.....#####.##.#..#.##..#...######.#####....
output:
9
result:
ok single line: '9'
Test #66:
score: 0
Accepted
time: 11ms
memory: 4352kb
input:
45 1194 5 4 632 37 206 ...#..#............#..........#..##....##......#...##..#..#.............#...#...........##....#.........#.#.##..........#......#..........#.....#...........#........#.#.................#................#..........##.......................#.....#..........#........#........#......
output:
0
result:
ok single line: '0'
Test #67:
score: -16
Time Limit Exceeded
input:
244 245 244 28 168 222 200 ...#...................................................................................................................................................................#..............................................................#.............. ..............................
output:
result:
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%