Submission #155392

# Submission time Handle Problem Language Result Execution time Memory
155392 2019-09-27T18:56:33 Z brcode Portals (BOI14_portals) C++14
0 / 100
2 ms 760 KB
#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(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]){
                dpl[i][j] = hold;
            }else{
                hold = j;
            }

        }
    }

    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]){
                dpr[i][j] = hold;
            }else{
                hold = j;
            }
        }
    }

    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]){
                dpu[j][i] = hold;
            }else{
                hold = j;
            }
        }
    }

    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]){
                dpd[j][i] = hold;
            }else{
                hold = i;
            }
        }
    }

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

            }
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Incorrect 2 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Incorrect 2 ms 632 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Incorrect 2 ms 760 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Incorrect 2 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Incorrect 2 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -