Submission #39877

#	Time	Username	Problem	Language	Result	Execution time	Memory
39877		Waschbar	Portals (BOI14_portals)	C++14	100 / 100	900 ms	111976 KiB

portals

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

const int INF = 1e8;
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];
vector < vector < int > > diss(MAXN+1,vector <int>(MAXN+1,INF));
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}});
            dist[i][j] = 0;
        }
        else{
            if(i == 1 || j == 1 || i == n || j == m) {
                st.insert({1,{i,j}});
                dist[i][j] = 1;
            }
        }
    }

    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, y = m;
        for(int j = 1; j <= m; j++){
            L[i][j] = x;
            if(g[i][j] == '#') x = j+1;
            R[i][m-j+1] = y;
            if(g[i][m-j+1] == '#') y = m-j;
        }
     }

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

}

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;
        diss[x][y] = dis;
        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] && diss[xx][yy] > dis+dist[x][y]) {
            st.insert({dis+dist[x][y],{xx,yy}});
            diss[xx][yy] = dis+dist[x][y];
        }
        xx = x; yy = R[x][y];
        if(!used[xx][yy]&& diss[xx][yy] > dis+dist[x][y]) {
            st.insert({dis+dist[x][y],{xx,yy}});
            diss[xx][yy] = dis+dist[x][y];
        }
        xx = U[x][y]; yy = y;
        if(!used[xx][yy] && diss[xx][yy] > dis+dist[x][y]) {
            st.insert({dis+dist[x][y],{xx,yy}});
            diss[xx][yy] = dis+dist[x][y];
        }
        xx = D[x][y]; yy = y;
        if(!used[xx][yy] && diss[xx][yy] > dis+dist[x][y]) {
            st.insert({dis+dist[x][y],{xx,yy}});
            diss[xx][yy] = dis+dist[x][y];
        }

        if(x < n && g[x+1][y] != '#' && !used[x+1][y] && diss[x+1][y] > dis+1) {
            st.insert({dis+1,{x+1,y}});
            diss[x+1][y] = dis+1;
        }
        if(x > 1 && g[x-1][y] != '#' && !used[x-1][y] && diss[x-1][y] > dis+1) {
            st.insert({dis+1,{x-1,y}});
            diss[x-1][y] = dis+1;
        }
        if(y < m && g[x][y+1] != '#' && !used[x][y+1] && diss[x][y+1] > dis+1) {
            st.insert({dis+1,{x,y+1}});
            diss[x][y+1] = dis+1;
        }
        if(y > 1 && g[x][y-1] != '#' && !used[x][y-1] && diss[x][y-1] > dis+1) {
            st.insert({dis+1,{x,y-1}});
            diss[x][y-1] = dis+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: 30 / 30