Submission #39859

#	Time	Username	Problem	Language	Result	Execution time	Memory
39859		Waschbar	Portals (BOI14_portals)	C++14	20 / 100	11 ms	19796 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];
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_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;
        }
     }

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

}

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();

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

    }

}

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