QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#361224#411. Dangerous SkatingMaster0 5ms21880kbC++143.6kb2024-03-22 23:29:462024-03-22 23:29:48

Judging History

This is the latest submission verdict.

  • [2024-03-22 23:29:48]
  • Judged
  • Verdict: 0
  • Time: 5ms
  • Memory: 21880kb
  • [2024-03-22 23:29:46]
  • 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));
    deque<int> q;
    q.push_back(F(sx,sy));
    d[F(sx,sy)] = 0;
    while (q.size()){
        int x = q.front(); q.pop_front();
        // 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;
                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: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 14784kb

input:

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

output:

7

result:

wrong answer 1st lines differ - expected: '6', found: '7'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 65
Accepted
time: 5ms
memory: 20652kb

input:

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

output:

69

result:

ok single line: '69'

Test #12:

score: -65
Wrong Answer
time: 3ms
memory: 21880kb

input:

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

output:

28

result:

wrong answer 1st lines differ - expected: '27', found: '28'

Subtask #3:

score: 0
Runtime Error

Test #27:

score: 0
Runtime Error

input:

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

output:


result: