제출 #39875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39875		Waschbar	포탈들 (BOI14_portals)	C++14	70 / 100	1000 ms	77488 KiB

portals

#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;

const long long INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 1e3;

int n, m;
bool used[MAXN+1][MAXN+1], vis[MAXN+1][MAXN+1];
int dist[MAXN+1][MAXN+1];
char g[MAXN+1][MAXN+1];
int L[MAXN+1][MAXN+1], R[MAXN+1][MAXN+1],
    U[MAXN+1][MAXN+1], D[MAXN+1][MAXN+1];

void calc_dist() {
    multiset <pair<int,pair<int,int> > > st;
    multiset <pair<int,pair<int,int> > > :: iterator it;

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) {
        if(g[i][j] == '#')
            st.insert({0,{i,j}});
        else{
            if(i == 1 || j == 1 || i == n || j == m)
                st.insert({1,{i,j}});
        }
    }

    while(!st.empty()) {
        it = st.begin();
        int x = it->nd.st;
        int y = it->nd.nd;
        vis[x][y] = 1;
        int dis = it->st;
        dist[x][y] = dis;
        st.erase(st.begin());


        if(x < n && g[x+1][y] != '#' && !vis[x+1][y])
            st.insert({dis+1,{x+1,y}});
        if(x > 1 && g[x-1][y] != '#' && !vis[x-1][y])
            st.insert({dis+1,{x-1,y}});
        if(y < m && g[x][y+1] != '#' && !vis[x][y+1])
            st.insert({dis+1,{x,y+1}});
        if(y > 1 && g[x][y-1] != '#' && !vis[x][y-1])
            st.insert({dis+1,{x,y-1}});

        while(!st.empty()){
            it = st.begin();
            if(vis[it->nd.st][it->nd.nd]) st.erase(st.begin());
            else break;
        }
    }

   /* for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++)
        cout << dist[i][j] << " ";
        cout << endl;
    }*/

}


void calc_LRPU() {

     for(int i = 1; i <= n; i++){
        int x = 1;
        for(int j = 1; j <= m; j++){
            L[i][j] = x;
            if(g[i][j] == '#') x = j+1;
        }
        x = m;
        for(int j = m; j >= 1; j--){
            R[i][j] = x;
            if(g[i][j] == '#') x = j-1;
        }
     }

     for(int j = 1; j <= m; j++){
        int x = 1;
        for(int i = 1; i <= n; i++){
            U[i][j] = x;
            if(g[i][j] == '#') x = i+1;
        }
        x = n;
        for(int i = n; i >= 1; i--){
            D[i][j] = x;
            if(g[i][j] == '#') x = i-1;
        }
     }

}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    cin >> n >> m;

    int x, y;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++){
        cin >> g[i][j];
        if(g[i][j] == 'S') x = i, y = j;
    }

    calc_LRPU();
    calc_dist();

    multiset < pair< int,pair<int,int> > > st;
    multiset < pair< int,pair<int,int> > > :: iterator it;

    st.insert({0,{x,y}});

    while(!st.empty()) {
        it = st.begin();
        x = it->nd.st;
        y = it->nd.nd;
        used[x][y] = 1;
        int dis = it->st;
        st.erase(st.begin());

        //cout << x << " " << y << " " << dis << endl;

        if(g[x][y] == 'C'){
            cout << dis; return 0;
        }

        int xx, yy;
        xx = x; yy = L[x][y];
        if(!used[xx][yy])
            st.insert({dis+dist[x][y],{xx,yy}});
        xx = x; yy = R[x][y];
        if(!used[xx][yy])
            st.insert({dis+dist[x][y],{xx,yy}});
        xx = U[x][y]; yy = y;
        if(!used[xx][yy])
            st.insert({dis+dist[x][y],{xx,yy}});
        xx = D[x][y]; yy = y;
        if(!used[xx][yy])
            st.insert({dis+dist[x][y],{xx,yy}});

        if(x < n && g[x+1][y] != '#' && !used[x+1][y])
            st.insert({dis+1,{x+1,y}});
        if(x > 1 && g[x-1][y] != '#' && !used[x-1][y])
            st.insert({dis+1,{x-1,y}});
        if(y < m && g[x][y+1] != '#' && !used[x][y+1])
            st.insert({dis+1,{x,y+1}});
        if(y > 1 && g[x][y-1] != '#' && !used[x][y-1])
            st.insert({dis+1,{x,y-1}});

        while(!st.empty()){
            it = st.begin();
            if(used[it->nd.st][it->nd.nd]) st.erase(st.begin());
            else break;
        }

    }



}


/*
5 7
S.#....
.#..##.
.......
#.#...#
.#C.##.
10 10
....C....#
.#.#...#..
......#.##
.##.......
#....#.##.
..##.#.#..
.#...#..#.
..###..#..
#...#.#S.#
..#.......

*/

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