QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#365005#5514. Mazeksu_#0 11ms4352kbC++142.2kb2024-03-24 17:59:302024-07-04 03:31:09

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 03:31:09]
  • 评测
  • 测评结果:0
  • 用时:11ms
  • 内存:4352kb
  • [2024-03-24 17:59:30]
  • 提交

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%