Submission #466815

#	Time	Username	Problem	Language	Result	Execution time	Memory
466815		M4mou	Portals (BOI14_portals)	C++17	20 / 100	12 ms	6560 KiB

portals

#include <bits/stdc++.h>

using namespace std;
char grid[1005][1005];
int dis[1005][1005], closestWall[1005][1005];
bool v[1005][1005];
int rowsLeft[1005][1005], rowsRight[1005][1005], colsUp[1005][1005],
        colsDown[1005][1005];
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};

#define pii pair<int,int>
#define piii pair<int,pii>
#define viii vector<piii>
#define fi first
#define se second

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(grid, '#' , sizeof grid);


    int n, m; cin >> n >> m;
    for(int i = 0;i<=n+1;i++)for(int j =0;j<=m+1;j++)dis[i][j] = INT_MAX;

    pii start;
    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);
        }

    queue<piii> bfs;
    for(int i = 0;i<n+2;i++)for(int j =0;j<m+2;j++){
            if(grid[i][j] == '#'){
                bfs.push({0,{i,j}});
                closestWall[i][j] = 0;
                v[i][j] = 1;
            }
        }
    while(bfs.size()){
        auto p = bfs.front();
        bfs.pop();
        for(int i = 0;i<4;i++){
            int x = p.se.fi;
            int y = p.se.se;
            if(x <0 || x >= n + 2 || y < 0 || y >= m+2 || v[x][y])continue;
            closestWall[x][y] = p.fi + 1;
            v[x][y] = 1;
            bfs.push({p.fi + 1, {x,y}});
        }
    }
    n += 2;
    m +=2;
    for(int i = 0;i<n;i++){
        for(int j =0;j<m;j++){
            if(grid[i][j] == '#')rowsLeft[i][j] = j;
            else rowsLeft[i][j] = rowsLeft[i][j-1];
        }
    }

    for(int i = 0;i<n;i++){
        for(int j =m-1;j>=0;j--){
            if(grid[i][j] == '#')rowsRight[i][j] = j;
            else rowsRight[i][j] = rowsRight[i][j+1];
        }
    }

    for(int i = 0;i<m;i++){
        for(int j =0;j<n;j++){
            if(grid[j][i] == '#')colsUp[j][i] = j;
            else colsUp[j][i] = colsUp[j-1][i];
        }
    }

    for(int i = 0;i<m;i++){
        for(int j =n-1;j>=0;j--){
            if(grid[j][i] == '#')colsDown[j][i] = j;
            else colsDown[j][i] = colsDown[j+1][i];
        }
    }

    priority_queue<piii, viii, greater<piii>> pq;
    pq.push({0,start});
    dis[start.first][start.second] = 0;
    while(pq.size()){
        pii next0 = pq.top().se; int dist = pq.top().fi; pq.pop();
        if (grid[next0.first][next0.second] == 'C'){
            cout << dist << endl;
            return 0;
        }
        int x = next0.fi, y = next0.se;
        if(v[x][y])continue;
        v[x][y] = 1;
        for(int i = 0;i<4;i++){
            int x0 = x + nx[i];
            int y0 = y + ny[i];
            if(grid[x0][y0] == '#' || v[x0][y0] || dis[x0][y0] <= dist + 1)continue;
            pq.push({dist +1 , {x0,y0}});
            dis[x0][y0] = dist + 1;
        }
        int newdistance = dist + closestWall[x][y] + 1;
        int up = colsUp[x][y] + 1;
        int down = colsDown[x][y] - 1 ;
        int right = rowsRight[x][y] - 1;
        int left = rowsLeft[x][y] + 1;
        if(dis[up][y] > newdistance){
            pq.push({newdistance, {up,y}});
            dis[up][y] = newdistance;
        }
        if (dis[down][y] > newdistance){
            pq.push({newdistance, {down,y}}); dis[down][y] = newdistance;
        }
        if (dis[x][right] > newdistance){
            pq.push({newdistance, {x,right}}); dis[x][right] = newdistance;
        }
        if (dis[x][left] > newdistance){
            pq.push({newdistance, {x,left}}); dis[x][left] = newdistance;
        }
    }
}

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