oj.uz

답안 #943260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943260 2024-03-11T09:44:27 Z salmon 포탈들 (BOI14_portals) C++14
70 / 100
 506 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

int R;
int C;
int x,y;
int gx,gy;
int sx,sy;
char c;
int lst[1100][1100];
int nextr[1100][1100];
int nextc[1100][1100];
int prevr[1100][1100];
int prevc[1100][1100];
bool vis[1100][1100];
vector<vector<int>> noom[2100100];
int dw[1100][1100];
int d[1100][1100];


priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
queue<vector<int>> q;

vector<pair<int,int>> bah = {{0,-1},{0,1},{1,0},{-1,0}};

bool valid(int i, int j){
    if(i >= 0 && i < R && 0 <= j && j < C) return true;
    return false;
}

int main(){
    scanf(" %d",&R);
    scanf(" %d",&C);

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            scanf(" %c",&c);
            if(c == '#'){
                lst[i][j] = 1;
            }
            else{
                lst[i][j] = 0;
            }

            if(c == 'C'){
                gx = i;
                gy = j;
            }
            if(c == 'S'){
                sx = i;
                sy = j;
            }

            d[i][j] = -1;
            dw[i][j] = -1;
        }
    }

    for(int i = 0; i < R; i++){
        vector<int> s;

        for(int j = 0; j < C; j++){
            while(!s.empty() && lst[i][j] == 1){
                nextr[i][s.back()] = j;
                s.pop_back();
            }
            s.push_back(j);
        }

        while(!s.empty()){
            nextr[i][s.back()] = C;
            s.pop_back();
        }
    }

    for(int j = 0; j < C; j++){
        vector<int> s;

        for(int i = 0; i < R; i++){
            while(!s.empty() && lst[i][j] == 1){
                nextc[s.back()][j] = i;
                s.pop_back();
            }
            s.push_back(i);
        }

        while(!s.empty()){
            nextc[s.back()][j] = R;
            s.pop_back();
        }
    }


    for(int i = 0; i < R; i++){
        vector<int> s;

        for(int j = C - 1; j >= 0; j--){
            while(!s.empty() && lst[i][j] == 1){
                prevr[i][s.back()] = j;
                s.pop_back();
            }
            s.push_back(j);
        }

        while(!s.empty()){
            prevr[i][s.back()] = -1;
            s.pop_back();
        }
    }

    for(int j = 0; j < C; j++){
        vector<int> s;

        for(int i = R - 1; i >= 0; i--){
            while(!s.empty() && lst[i][j] == 1){
                prevc[s.back()][j] = i;
                s.pop_back();
            }
            s.push_back(i);
        }

        while(!s.empty()){
            prevc[s.back()][j] = -1;
            s.pop_back();
        }
    }

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            if(lst[i][j] == 1) q.push({i,j,0});
        }
    }

    for(int i = 0; i < R; i++){
        q.push({i,0,1});
        q.push({i,C-1,1});
    }

    for(int i = 0; i < C; i++){
        q.push({0,i,1});
        q.push({R-1,i,1});
    }

    while(!q.empty()){
        vector<int> v = q.front();
        q.pop();
        int i = v[0];
        int j = v[1];

        if(dw[i][j] != -1) continue;

        dw[i][j] = v[2];

        for(pair<int,int> ii : bah){
            int ni = ii.first + i;
            int nj = ii.second + j;

            if(valid(ni,nj) && dw[ni][nj] == -1){
                q.push({ni,nj,v[2] + 1});
            }
        }
    }


    noom[0].push_back({0,sx,sy});
    //pq.push({0,sx,sy,false});

    for(int i = 0; i <= R * C; i++){

       for(vector<int> v : noom[i]){
            int i = v[1];
            int j = v[2];
            int de = v[0];

            if(d[i][j] != -1) continue;
            if(lst[i][j] == 1) continue;

            d[i][j] = de;

            for(pair<int,int> ii : bah){
                int ni = ii.first + i;
                int nj = ii.second + j;

                if(valid(ni,nj) && lst[ni][nj] != 1 && d[ni][nj] == -1){
                    noom[de + 1].push_back({de+1,ni,nj});
                }
            }

            if(d[i][prevr[i][j] + 1] == -1) noom[de + dw[i][j]].push_back({de + dw[i][j],i,prevr[i][j] + 1});
            if(d[i][nextr[i][j] - 1] == -1) noom[de + dw[i][j]].push_back({de + dw[i][j],i,nextr[i][j] - 1});
            if(d[prevc[i][j] + 1][j] == -1) noom[de + dw[i][j]].push_back({de + dw[i][j],prevc[i][j] + 1,j});
            if(d[nextc[i][j] - 1][j] == -1) noom[de + dw[i][j]].push_back({de + dw[i][j],nextc[i][j] - 1,j});
       }
    }

    /*for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            printf("%d ",dw[i][j]);
        }
        printf("\n");
    }*/

    printf("%d",d[gx][gy]);

}
/*
5 4
G#.#
.#.#
...#
S..#
....
*/

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf(" %d",&R);
      |     ~~~~~^~~~~~~~~~
portals.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf(" %d",&C);
      |     ~~~~~^~~~~~~~~~
portals.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |             scanf(" %c",&c);
      |             ~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 64028 KB Output is correct
2 Correct 13 ms 64252 KB Output is correct
3 Correct 13 ms 64092 KB Output is correct
4 Correct 14 ms 63832 KB Output is correct
5 Correct 15 ms 64092 KB Output is correct
6 Correct 13 ms 64092 KB Output is correct
7 Correct 13 ms 64092 KB Output is correct
8 Correct 14 ms 64092 KB Output is correct
9 Correct 13 ms 63836 KB Output is correct
10 Correct 13 ms 63832 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 63836 KB Output is correct
2 Correct 13 ms 64092 KB Output is correct
3 Correct 13 ms 64092 KB Output is correct
4 Correct 14 ms 64032 KB Output is correct
5 Correct 14 ms 64088 KB Output is correct
6 Correct 16 ms 64092 KB Output is correct
7 Correct 13 ms 64092 KB Output is correct
8 Correct 13 ms 63952 KB Output is correct
9 Correct 14 ms 66392 KB Output is correct
10 Correct 14 ms 66652 KB Output is correct
11 Correct 14 ms 66496 KB Output is correct
12 Correct 14 ms 66396 KB Output is correct
13 Correct 14 ms 66560 KB Output is correct
14 Correct 13 ms 63836 KB Output is correct
15 Correct 14 ms 66392 KB Output is correct
16 Correct 13 ms 63836 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 63836 KB Output is correct
2 Correct 13 ms 64012 KB Output is correct
3 Correct 13 ms 64344 KB Output is correct
4 Correct 13 ms 64104 KB Output is correct
5 Correct 28 ms 71512 KB Output is correct
6 Correct 28 ms 71448 KB Output is correct
7 Correct 28 ms 72028 KB Output is correct
8 Correct 26 ms 71516 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 63912 KB Output is correct
2 Correct 13 ms 64092 KB Output is correct
3 Correct 15 ms 64092 KB Output is correct
4 Correct 13 ms 64072 KB Output is correct
5 Correct 14 ms 64092 KB Output is correct
6 Correct 13 ms 64092 KB Output is correct
7 Correct 13 ms 63964 KB Output is correct
8 Correct 13 ms 64092 KB Output is correct
9 Correct 15 ms 66612 KB Output is correct
10 Correct 17 ms 66900 KB Output is correct
11 Correct 14 ms 66396 KB Output is correct
12 Correct 14 ms 66396 KB Output is correct
13 Correct 14 ms 66392 KB Output is correct
14 Correct 28 ms 71512 KB Output is correct
15 Correct 28 ms 71516 KB Output is correct
16 Correct 33 ms 72020 KB Output is correct
17 Correct 28 ms 72284 KB Output is correct
18 Correct 30 ms 73300 KB Output is correct
19 Correct 33 ms 73552 KB Output is correct
20 Correct 35 ms 77564 KB Output is correct
21 Correct 29 ms 71516 KB Output is correct
22 Correct 28 ms 71512 KB Output is correct
23 Correct 28 ms 71516 KB Output is correct
24 Correct 25 ms 73296 KB Output is correct
25 Correct 14 ms 64504 KB Output is correct
26 Correct 14 ms 66396 KB Output is correct
27 Correct 13 ms 64012 KB Output is correct
28 Correct 26 ms 71516 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 63836 KB Output is correct
2 Correct 14 ms 63936 KB Output is correct
3 Correct 13 ms 64092 KB Output is correct
4 Correct 13 ms 63836 KB Output is correct
5 Correct 13 ms 63952 KB Output is correct
6 Correct 13 ms 64092 KB Output is correct
7 Correct 13 ms 63956 KB Output is correct
8 Correct 15 ms 64092 KB Output is correct
9 Correct 15 ms 66392 KB Output is correct
10 Correct 15 ms 66652 KB Output is correct
11 Correct 14 ms 66396 KB Output is correct
12 Correct 14 ms 66308 KB Output is correct
13 Correct 15 ms 66556 KB Output is correct
14 Correct 29 ms 71512 KB Output is correct
15 Correct 28 ms 71516 KB Output is correct
16 Correct 28 ms 72016 KB Output is correct
17 Correct 28 ms 72284 KB Output is correct
18 Correct 32 ms 73300 KB Output is correct
19 Correct 27 ms 73560 KB Output is correct
20 Correct 34 ms 77404 KB Output is correct
21 Correct 29 ms 71512 KB Output is correct
22 Correct 27 ms 71504 KB Output is correct
23 Correct 29 ms 71516 KB Output is correct
24 Correct 506 ms 193544 KB Output is correct
25 Correct 379 ms 195216 KB Output is correct
26 Correct 486 ms 248908 KB Output is correct
27 Runtime error 398 ms 262144 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -