Submission #155763

#	Time	Username	Problem	Language	Result	Execution time	Memory
155763		brcode	Portals (BOI14_portals)	C++14	100 / 100	506 ms	64188 KiB

portals

#include <iostream>
#include <queue>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
int n,m;
char grid[MAXN][MAXN];
pair<int,int> start;
bool portal[MAXN][MAXN];
vector<pair<int,int>> portals;
queue<pair<int,int>> q1;
priority_queue<pair<int,pair<int,int>>> pq;
pair<int,int> finish;
int dx[5] = {1,0,-1,0};
int dy[5] = {0,1,0,-1};
int portall[MAXN][MAXN];
int portald[MAXN][MAXN];
int portalr[MAXN][MAXN];
int portalu[MAXN][MAXN];
int dp[MAXN][MAXN];
int dpl[MAXN][MAXN];
int dpr[MAXN][MAXN];
int dpu[MAXN][MAXN];
int dpd[MAXN][MAXN];
int dist[MAXN][MAXN];
bool check(int x,int y){
    if(x<=n && x>=1 && y<=m && y>=1){
        return true;
    }
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>grid[i][j];
            if(grid[i][j] == 'S'){
                start = make_pair(i,j);
               // cout<<i<<" "<<j<<endl;
            }
            if(grid[i][j] == 'C'){
                finish = make_pair(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        grid[i][0] = '#';
        grid[i][m+1] = '#';
    }
    for(int i=1;i<=m;i++){
        grid[0][i] = '#';
        grid[n+1][i] = '#';
    }
 
    grid[0][0] = '#';
    grid[0][m+1] = '#';
    grid[n+1][0] = '#';
    grid[n+1][m+1] = '#';
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(grid[i][j] == '#'){
                for(int k=0;k<4;k++){
                    int x2 = i+dx[k];
                    int y2 = j+dy[k];
 
                    if(check(x2,y2) && grid[x2][y2]!='#'){
                        //if within grid and surrounding cell is a movable cell, place a portal here
                        //int dx[5] = {1,0,-1,0};
                        //int dy[5] = {0,1,0,-1};
                        if(k==0){
                            portalu[x2][y2] = true;
                        }
                        if(k==1){
                            portall[x2][y2] = true;
                        }
                        if(k==2){
                            portald[x2][y2] = true;
                        }
                        if(k==3){
                            portalr[x2][y2] = true;
                        }
                        portal[x2][y2] = true;
                        portals.push_back(make_pair(x2,y2));
                    }
                }
            }
 
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dist[i][j] = 1e9;
            dp[i][j] = 1e9;
        }
    }
    for(auto x:portals){
        q1.push(x);
 
       // cout<<x.first<<" "<<x.second<<endl;
        dist[x.first][x.second] = 0;
    }
    while(!q1.empty()){
        auto hold =q1.front();
        q1.pop();
        int x = hold.first;
        int y = hold.second;
        for(int i=0;i<4;i++){
            int x2 = x+dx[i];
            int y2 = y+dy[i];
            if(check(x2,y2) && dist[x2][y2]==1e9 && grid[x2][y2]!='#'){
 
                dist[x2][y2] = dist[x][y]+1;
                q1.push(make_pair(x2,y2));
            }
        }
    }
 
    for(int i=1;i<=n;i++){
        int hold = 1;
        for(int j=1;j<=m;j++){
            if(grid[i][j] == '#'){
                continue;
            }
            if(portall[i][j]){
                hold = j;
            }
            dpl[i][j] = hold;
            
        }
    }
 
    for(int i=1;i<=n;i++){
        int hold = m;
        for(int j=m;j>=1;j--){
            if(grid[i][j] == '#'){
                continue;
            }
            if(portalr[i][j]){
                hold = j;
            }
            dpr[i][j] = hold;
            
        }
    }
 
    for(int i=1;i<=m;i++){
        int hold = 1;
        for(int j=1;j<=n;j++){
            if(grid[j][i] == '#'){
                continue;
            }
            if(portalu[j][i]){
                hold = j;
            }
            
            dpu[j][i] = hold;

            
        }
    }
 
    for(int i=1;i<=m;i++){
        int hold = n;
        for(int j=n;j>=1;j--){
            if(grid[j][i] == '#'){
                continue;
            }
            if(portald[j][i]){
                hold =j;
            }
            dpd[j][i] = hold;
            
        }
    }

    pq.push(make_pair(0,start));
    dp[start.first][start.second] = 0;
    while(!pq.empty()){
        auto hold = pq.top();
        pq.pop();
        int w = hold.first;
 
        int x = hold.second.first;
        int y = hold.second.second;
 
        if(x == finish.first && y == finish.second){
            cout<<-1*w<<endl;
            return 0;
        }
        for(int i=0;i<4;i++){
            int x2 = x+dx[i];
            int y2 = y+dy[i];
            if(check(x2,y2) && grid[x2][y2]!='#' && dp[x2][y2]>dp[x][y]+1){
                dp[x2][y2] = dp[x][y]+1;
                pq.push(make_pair(-1*dp[x2][y2],make_pair(x2,y2)));
 
            }
            int p = dpl[x][y];
            if(check(x,p) && grid[x][p] != '#' && dp[x][p]>dp[x][y]+dist[x][y]+1){
                dp[x][p]=dp[x][y]+dist[x][y]+1;
                pq.push(make_pair(-1*dp[x][p],make_pair(x,p)));
 
            }
            p = dpr[x][y];
 
            if(check(x,p) && grid[x][p] != '#' && dp[x][p]>dp[x][y]+dist[x][y]+1){
                dp[x][p]=dp[x][y]+dist[x][y]+1;
                pq.push(make_pair(-1*dp[x][p],make_pair(x,p)));
 
            }
            p = dpu[x][y];
            if(x == 4 && y == 3){
                //cout<<123<<" "<<p<<endl;
                //cout<<dp[p][y]<<" "<<dp[x][y]+dist[x][y]+1<<endl;
            }
            if(check(p,y) && grid[p][y] != '#' && dp[p][y]>dp[x][y]+dist[x][y]+1){
                dp[p][y]=dp[x][y]+dist[x][y]+1;
                pq.push(make_pair(-1*dp[p][y],make_pair(p,y)));
 
            }
            p = dpd[x][y];
            if(check(p,y) && grid[p][y] != '#' && dp[p][y]>dp[x][y]+dist[x][y]+1){
                dp[p][y]=dp[x][y]+dist[x][y]+1;
                pq.push(make_pair(-1*dp[p][y],make_pair(p,y)));
 
            }
        }
    }
}

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