제출 #394816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394816		Sara	포탈들 (BOI14_portals)	C++14	100 / 100	933 ms	184772 KiB

portals

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define F first
#define S second
#define pb push_back
#define md ((b + e) >> 1)

const ll N = 1000 + 3;
const ll LOG = 17;
const ll INF = 1e9 + 5;
const ll MOD = 1e9 + 7;

short n, m;
char mat[N][N];
pair <short, short> L[N][N], R[N][N];
pair <short, short> U[N][N], D[N][N];
pair <int, int> dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector <int> g[N * N];
vector < pair < int, int > > adj[N * N];
pair <short, short> st, en;
bool A[N][N];
int id[N][N], ID = 1;

inline bool in_sq(short x, short y){
    return ((0 <= x) && (x <= n + 1) && (0 <= y) && (y <= m + 1));
}

inline bool valid(short x, short y){
    return (in_sq(x, y) && !A[x][y]); 
}

inline void add_edges(){
    for (short i = 0; i <= n + 1; i ++){
        for (short j = 0; j <= m + 1; j ++){
            for (short d = 0; d < 4; d ++){
                short x = i + dir[d].F;
                short y = j + dir[d].S;
                if (valid(x, y)){
                    g[id[i][j]].pb(id[x][y]);
                }
            }
        }
    } 
    return;
}

int dis[N * N];
queue <int> q;

inline void bfs(){
    for (short i = 0; i <= n + 1; i ++){
        for (short j = 0; j <= m + 1; j ++){
            dis[id[i][j]] = INF;
        }
    }
    for (short i = 0; i <= n + 1; i ++){
        for (short j = 0; j <= m + 1; j ++){
            if (A[i][j]){
                dis[id[i][j]] = 0;
                q.push(id[i][j]);
            }
        }
    }

    while (q.size()){
        int v = q.front();
        q.pop();
        for (auto u : g[v]){
            if (dis[v] + 1 < dis[u]){
                dis[u] = dis[v] + 1;
                q.push(u);
            }
        }
    }
    return;
}

inline void pre(){

    for (short i = 0; i <= n + 1; i ++){
        for (short j = 0; j <= m + 1; j ++){
            if (A[i][j]){
                L[i][j] = {i, j};
                U[i][j] = {i, j};
            }
            else {
                L[i][j] = L[i][j - 1];
                U[i][j] = U[i - 1][j];
            }
        }
    }

    for (short i = n + 1; i >= 0; i --){
        for (short j = m + 1; j >= 0; j --){
            if (A[i][j]){
                R[i][j] = {i, j};
                D[i][j] = {i, j};
            }
            else {
                R[i][j] = R[i][j + 1];
                D[i][j] = D[i + 1][j];
            }
        }
    }

    return;
}

inline void add_edges2(){
    for (short i = 0; i <= n + 1; i ++){
        for (short j = 0; j <= m + 1; j ++){

            if (!valid(i, j)) continue;

            if (valid(i + 1, j)){
                short x = D[i + 1][j].F - 1;
                short y = D[i + 1][j].S;
                if (!valid(x, y)) continue;
                adj[id[i][j]].pb({id[x][y], dis[id[i][j]]});

            }
            if (valid(i, j + 1)){
                short x = R[i][j + 1].F;
                short y = R[i][j + 1].S - 1;
                if (!valid(x, y)) continue;
                adj[id[i][j]].pb({id[x][y], dis[id[i][j]]});
            }
            if (valid(i - 1, j)){
                short x = U[i - 1][j].F + 1;
                short y = U[i - 1][j].S; 
                if (!valid(x, y)) continue;
                adj[id[i][j]].pb({id[x][y], dis[id[i][j]]});
            }
            if (valid(i, j - 1)){
                short x = L[i][j - 1].F;
                short y = L[i][j - 1].S + 1;
                if (!valid(x, y)) continue;
                adj[id[i][j]].pb({id[x][y], dis[id[i][j]]});
            }
            for (short d = 0; d < 4; d ++){
                short x = i + dir[d].F;
                short y = j + dir[d].S;
                if (valid(x, y)){
                    adj[id[i][j]].pb({id[x][y], 1});
                }
            }
        }
    }
    return;
}

bool mark[N * N];
priority_queue < pair < ll, int > > pq;

inline void dij(){
    for (int i = 0; i <= n + 1; i ++){
        for (int j = 0; j <= m + 1; j ++){
            dis[id[i][j]] = INF;
        }
    }

    pq.push({0, id[st.F][st.S]});
    dis[id[st.F][st.S]] = 0;
    while (pq.size()){
        auto v = pq.top().S;
        pq.pop();
        if (mark[v]) continue;
        mark[v] = 1;
        if (v == id[en.F][en.S]) break;
        for (auto it : adj[v]){
            ll w = it.S;
            auto u = it.F;
            if (dis[v] + w < dis[u]){
                dis[u] = dis[v] + w;
                pq.push({-dis[u], u});
            }
        }
    }
    cout << dis[id[en.F][en.S]] << '\n';
    return;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            cin >> mat[i][j];
            if (mat[i][j] == 'S'){
                st = {i, j};
                mat[i][j] = '.';
            }
            if (mat[i][j] == 'C'){
                en = {i, j};
                mat[i][j] = '.';
            }
            A[i][j] = (mat[i][j] == '#');
        }
    }

    for (int i = 0; i <= n + 1; i ++){
        A[i][0] = A[i][m + 1] = 1;
    }
    
    for (int j = 0; j <= m + 1; j ++){
        A[0][j] = A[n + 1][j] = 1;
    }

    for (int i = 0; i <= n +1 ; i ++){
        for (int j = 0; j <= m + 1; j ++){
            id[i][j] = ID; ID ++;
        }
    }

    add_edges();
    bfs();
    pre();
    add_edges2();
    dij();

    return 0;
}

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