제출 #1057215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057215		NemanjaSo2005	포탈들 (BOI14_portals)	C++17	100 / 100	526 ms	67484 KiB

portals

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int inf = 2e9+7;

struct P{
    int x,y;
    bool operator==(P v){
        return v.x==x && v.y==y;
    }
    bool operator!=(P v){
        return v.x!=x || v.y!=y;
    }
};
bool operator<(const P a, const P b){
    if(a.x < b.x) return 1;
    if(a.x > b.x) return 0;
    return a.y < b.y;
}

int n, m;
string a[MAXN];
P b, e, nl = {-1,-1};
P d[MAXN][MAXN][4];
int c[MAXN][MAXN];
bool v[MAXN][MAXN];

void cc(){
    queue<pair<int,P>> q;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(a[i][j]=='#'){
                q.push({-1,P{i,j}});
            }
        }
    }
    int w;
    P p;
    while(!q.empty()){
        w = q.front().first+1, p = q.front().second;
        q.pop();
        int i = p.x, j = p.y;
        //cout << i << ' ' << j << '\n';
        if(i < 0 || j < 0 || i >= n ||j >= m) continue;
        if(v[i][j]) continue;
        v[i][j] = 1;
        c[i][j] = w-1;
        q.push({w,P{i-1,j}});
        q.push({w,P{i,j-1}});
        q.push({w,P{i+1,j}});
        q.push({w,P{i,j+1}});
    }
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j) v[i][j] = 0;
    }
}

void calc(){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            d[i][j][0] = (a[i][j] == '#' ? nl : (d[i-1][j][0] != nl ? d[i-1][j][0] : P{i,j}));
            d[i][j][3] = (a[i][j] == '#' ? nl : (d[i][j-1][3] != nl ? d[i][j-1][3] : P{i,j}));
        }
    }
    for(int i = n-1; i >= 0; --i){
        for(int j = m-1; j >= 0; --j){
            d[i][j][1] = (a[i][j] == '#' ? nl : (d[i][j+1][1] != nl ? d[i][j+1][1] : P{i,j}));
            d[i][j][2] = (a[i][j] == '#' ? nl : (d[i+1][j][2] != nl ? d[i+1][j][2] : P{i,j}));
        }
    }
}

bool da(P p){
    return v[p.x][p.y];
}

int dfs(){
    priority_queue<pair<int,P>, vector<pair<int,P>>, greater<pair<int,P>>> q;
    q.push({0,b});
    P p;
    int w;
    while(!q.empty()){
        w = q.top().first, p = q.top().second;
        q.pop();
        if(p == e) return w;
        ++w;
        int i = p.x, j = p.y;
        if(v[i][j]) continue;
        v[i][j] = 1;
        //cout << i << ' ' << j << ' ' << w << '\n';
        if(a[i-1][j]!='#') q.push({w, P{i-1,j}});
        if(a[i][j-1]!='#') q.push({w, P{i,j-1}});
        if(a[i+1][j]!='#') q.push({w, P{i+1,j}});
        if(a[i][j+1]!='#') q.push({w, P{i,j+1}});

        if(d[i][j][0]!=nl && !da(d[i][j][0])) q.push({w+c[i][j], d[i][j][0]});
        if(d[i][j][1]!=nl && !da(d[i][j][1])) q.push({w+c[i][j], d[i][j][1]});
        if(d[i][j][2]!=nl && !da(d[i][j][2])) q.push({w+c[i][j], d[i][j][2]});
        if(d[i][j][3]!=nl && !da(d[i][j][3])) q.push({w+c[i][j], d[i][j][3]});
    }
    return -1;
}


void solve(){
    cin >> n >> m;
    for(int i = 0; i < m+2; ++i){
        a[0] += "#";
        a[n+1] += "#";
    }
    for(int i = 0; i++ < n;){
        cin >> a[i];
        a[i] = "#" + a[i] + "#";
        for(int j = 0; j++ < m;){
            if(a[i][j] == 'S') b = P{i,j};
            if(a[i][j] == 'C') e = P{i,j};
        }
    }
    n += 2; m += 2;
    //for(int i = 0; i < n; ++i) cout << a[i] << '\n';
    cc();
    calc();
    cout << dfs();
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int q=1;
    //cin >> q;
    while(q--){solve();}
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30