QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#361231#411. Dangerous SkatingMaster78 9ms25108kbC++143.7kb2024-03-22 23:47:252024-03-22 23:47:26

Judging History

This is the latest submission verdict.

  • [2024-03-22 23:47:26]
  • Judged
  • Verdict: 78
  • Time: 9ms
  • Memory: 25108kb
  • [2024-03-22 23:47:25]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;

int n,m;

int sx,sy,tx,ty;

int head[N * N], ver[(N * N) << 1], nxt[(N * N) << 1], edge[(N * N) << 1], tot;

char a[N][N];

void add(int x,int y,int z){
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

int Next[N][N][4];

// shang: 0, xia: 1, zuo: 2, you: 3

int F(int x,int y){
    return (x - 1) * m + y;
}

int d[N * N];

bool v[N * N];

void bfs(){
    memset(d,0x3f,sizeof(d));
    priority_queue<pair<int,int>> q;
    q.push({0,F(sx,sy)});
    d[F(sx,sy)] = 0;
    while (q.size()){
        int x = q.top().second; q.pop();
        // cout << x << ' ' << d[x] << '\n';
        if (v[x]) continue;
        v[x] = 1;
        for (int i = head[x];i;i = nxt[i]){
            int y = ver[i], z = edge[i];
            // cout << "edge:" <<  x << ' ' << y << ' ' << z << '\n';
            if (d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push({-d[y],y});
                // if (z == 1)
                //     q.push_front(y);
                // else
                //     q.push_back(y);
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= n;i++)
        scanf("%s", a[i] + 1);
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    for (int j = 1;j <= m;j++){
        int pre = -1;
        for (int i = 1;i <= n;i++){
            if (a[i][j] == '.'){
                Next[i][j][0] = pre;
                if (pre == -1)
                    pre = F(i,j);
            }
            else
                pre = -1;
        }
    }
    for (int j = 1;j <= m;j++){
        int pre = -1;
        for (int i = n;i >= 1;i--){
            if (a[i][j] == '.'){
                Next[i][j][1] = pre;
                if (pre == -1)
                    pre = F(i,j);
            }
            else
                pre = -1;
        }
    }
    for (int i = 1;i <= n;i++){
        int pre = -1;
        for (int j = 1;j <= m;j++){
            if (a[i][j] == '.'){
                Next[i][j][2] = pre;
                if (pre == -1)
                    pre = F(i,j);
            }
            else
                pre = -1;
        }
    }
    for (int i = 1;i <= n;i++){
        int pre = -1;
        for (int j = m;j >= 1;j--){
            if (a[i][j] == '.'){
                Next[i][j][3] = pre;
                if (pre == -1)
                    pre = F(i,j);
            }
            else
                pre = -1;
        }
    }
    // for (int i = 1;i <= n;i++){
    //     for (int j = 1;j <= m;j++){
    //         cout << i << ' ' << j << ' ' << Next[i][j][3] << '\n';
    //     }
    // }
    // return 0;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            if (a[i][j] == '.'){
                if (a[i + 1][j] == '.' && F(i + 1,j) != Next[i][j][1])
                    add(F(i,j),F(i + 1,j),2);
                if (a[i][j + 1] == '.' && F(i,j + 1) != Next[i][j][3])
                    add(F(i,j),F(i,j + 1),2);
                if (a[i - 1][j] == '.' && F(i - 1,j) != Next[i][j][0])
                    add(F(i,j),F(i - 1,j),2);
                if (a[i][j - 1] == '.' && F(i,j - 1) != Next[i][j][2])
                    add(F(i,j),F(i,j - 1),2);
            }
        }
    }
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            for (int k = 0;k < 4;k++)
                if (Next[i][j][k] != -1 && a[i][j] == '.')
                    add(F(i,j),Next[i][j][k],1)/*, cout << k << ' ' << F(i,j) << ' ' << Next[i][j][k] << '\n'*/;
    // return 0;
    bfs();
    if (!v[F(tx,ty)]) d[F(tx,ty)] = -1;
    printf("%d",d[F(tx,ty)]);
    return 0;
}   

詳細信息

Subtask #1:

score: 13
Accepted

Test #1:

score: 13
Accepted
time: 0ms
memory: 16088kb

input:

10 10
##########
#....#.###
#.......##
#........#
#.......##
##.......#
#.......##
#.....#.##
#.....#..#
##########
4 7
8 5

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 2ms
memory: 16140kb

input:

10 10
##########
#.....#.##
#....#...#
#..#....##
#........#
#.#......#
#...##.#.#
#........#
#..#.....#
##########
9 9
9 8

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 16072kb

input:

10 10
##########
#..#.....#
#....#.#.#
##..#.##.#
##......##
##.#...#.#
#..#.##..#
#..###...#
##...#..##
##########
4 9
5 6

output:

10

result:

ok single line: '10'

Test #4:

score: 0
Accepted
time: 2ms
memory: 16072kb

input:

10 10
##########
##.#######
##.#.##.##
##.###.###
#.....#.##
#####..###
######...#
##....##.#
###.###.##
##########
8 9
4 3

output:

10

result:

ok single line: '10'

Test #5:

score: 0
Accepted
time: 2ms
memory: 16076kb

input:

10 10
##########
#.#.#....#
##..#....#
#...####.#
#.##.#..##
##..##..##
#..##..#.#
#.#....#.#
#....#...#
##########
4 9
2 2

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 16072kb

input:

10 10
##########
#........#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
##########
4 4
7 7

output:

10

result:

ok single line: '10'

Test #7:

score: 0
Accepted
time: 0ms
memory: 14436kb

input:

10 6
######
#....#
#....#
#....#
#....#
#....#
#....#
#....#
#....#
######
3 3
8 4

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 0ms
memory: 14936kb

input:

10 9
#########
##.....##
#.......#
#.......#
#....#..#
#.....#.#
#..#..#.#
#.#####.#
#.#....##
#########
5 4
9 5

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 2ms
memory: 14932kb

input:

10 10
##########
#..#.....#
#...##.#.#
#....#...#
#...#.#.##
#......#.#
#.......##
#...#..#.#
#......#.#
##########
2 3
2 3

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 2ms
memory: 16148kb

input:

10 10
##########
###......#
#..#...#.#
#....#...#
##......##
#........#
#..#...#.#
#.#.....##
#.....##.#
##########
2 9
5 4

output:

7

result:

ok single line: '7'

Subtask #2:

score: 65
Accepted

Test #11:

score: 65
Accepted
time: 9ms
memory: 19596kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................................

output:

69

result:

ok single line: '69'

Test #12:

score: 0
Accepted
time: 5ms
memory: 25108kb

input:

200 200
########################################################################################################################################################################################################
#....................................................................................#........

output:

27

result:

ok single line: '27'

Test #13:

score: 0
Accepted
time: 6ms
memory: 19612kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................#...............

output:

12

result:

ok single line: '12'

Test #14:

score: 0
Accepted
time: 4ms
memory: 21392kb

input:

200 200
########################################################################################################################################################################################################
#......#.......#....#.........#.......#....##.#..#.....#..#..#.....#....#...#.....#.#.#.......

output:

42

result:

ok single line: '42'

Test #15:

score: 0
Accepted
time: 5ms
memory: 18776kb

input:

200 200
########################################################################################################################################################################################################
#.#..#.###.#..#.##..#.....#.#.#.#.###.#.###..#.#...#.####..#####..###.....#..#..##.#...####...

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0
Accepted
time: 4ms
memory: 19748kb

input:

200 200
########################################################################################################################################################################################################
#...#.............##.#................................................#.#.....................

output:

28

result:

ok single line: '28'

Test #17:

score: 0
Accepted
time: 4ms
memory: 23508kb

input:

200 200
########################################################################################################################################################################################################
#.........#.......#............#...........#...#.............#.......................#........

output:

390

result:

ok single line: '390'

Test #18:

score: 0
Accepted
time: 0ms
memory: 19288kb

input:

200 200
########################################################################################################################################################################################################
#.....#.......................................#....................#...#........#....#........

output:

501

result:

ok single line: '501'

Test #19:

score: 0
Accepted
time: 9ms
memory: 21448kb

input:

200 200
########################################################################################################################################################################################################
#.........##.....#..........#.#..............##..#................#..................#........

output:

82

result:

ok single line: '82'

Test #20:

score: 0
Accepted
time: 0ms
memory: 21456kb

input:

190 200
########################################################################################################################################################################################################
#.............................................................................................

output:

110

result:

ok single line: '110'

Test #21:

score: 0
Accepted
time: 0ms
memory: 18784kb

input:

200 200
########################################################################################################################################################################################################
#..###...###...###...###...###...###...###...###...###...###...###...###...###...###...###....

output:

25350

result:

ok single line: '25350'

Test #22:

score: 0
Accepted
time: 0ms
memory: 20868kb

input:

200 195
###################################################################################################################################################################################################
#..................................................................................................

output:

12813

result:

ok single line: '12813'

Test #23:

score: 0
Accepted
time: 2ms
memory: 22736kb

input:

200 200
########################################################################################################################################################################################################
#....#....................#..#......#............#................#........#..................

output:

134

result:

ok single line: '134'

Test #24:

score: 0
Accepted
time: 4ms
memory: 24928kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................................

output:

191

result:

ok single line: '191'

Test #25:

score: 0
Accepted
time: 3ms
memory: 19144kb

input:

200 200
########################################################################################################################################################################################################
#....#.#................#....#.#...#.....#.....#.#.......#.#............#...#......#.#..#.....

output:

330

result:

ok single line: '330'

Test #26:

score: 0
Accepted
time: 7ms
memory: 20780kb

input:

200 200
########################################################################################################################################################################################################
#.......#...#.#..#......#......#....#...........#...#.........#.....#..#......##..#...........

output:

408

result:

ok single line: '408'

Subtask #3:

score: 0
Runtime Error

Test #27:

score: 0
Runtime Error

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:


result: