Submission #829796

#	Time	Username	Problem	Language	Result	Execution time	Memory
829796		BidoTeima	Portals (BOI14_portals)	C++17	100 / 100	861 ms	207508 KiB

portals

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int nearest_wall[N][N];
vector<array<int,3>>adj[N][N];
vector<int>walls_x[N],walls_y[N];
char grid[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int r,c;
bool check(int x, int y){
    return x>=1&&y>=1&&x<=r&&y<=c&&grid[x][y]!='#';
}
int main()
{ 
    memset(nearest_wall,0xf3f3f,sizeof(nearest_wall));
    cin>>r>>c; 
    int stx,sty,endx,endy;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            cin>>grid[i][j];
            if(grid[i][j]=='S')stx=i,sty=j;
            if(grid[i][j]=='C')endx=i,endy=j;
        }
    }
    queue<vector<int>>q;
    for(int i = 0; i <= r + 1; i++){
        grid[i][c+1]='#';
        grid[i][0]='#';
    }
    for(int i = 0; i <= c + 1; i++){
        grid[r+1][i]='#';
        grid[0][i]='#';
    }
    for(int i = 0; i <= r + 1; i++){
        for(int j = 0; j <= c + 1; j++){
            if(grid[i][j]!='#'){
                for(int k = 0; k < 4; k++){
                    if(check(i+dx[k],j+dy[k])){
                        adj[i][j].push_back({i+dx[k],j+dy[k],1});
                    }
                }
            }
            else{
                walls_x[i].push_back(j);
                walls_y[j].push_back(i);
                q.push({i, j, 0}); 
            }
        }
    }
    for(int i = 0; i <= r+1; i++)sort(walls_x[i].begin(),walls_x[i].end());
    for(int i = 0; i <= c+1; i++)sort(walls_y[i].begin(),walls_y[i].end());
    while(!q.empty()){
        int x = q.front()[0];
        int y = q.front()[1];
        int d = q.front()[2];
        q.pop();
        if(nearest_wall[x][y]<2e6)continue;
        nearest_wall[x][y]=d;
        for(int i = 0; i < 4; i++){
            if(x+dx[i]>=0&&x+dx[i]<=r+1&&y+dy[i]>=0&&y+dy[i]<=c+1){
                q.push({x+dx[i],y+dy[i],d+1});
            }
        }
    }
    for(int x = 0; x <= r+1; x++){
        for(int y = 0; y <= c+1; y++){ 
            if(grid[x][y]=='#')continue;
            // nearest wall to the left (<y)
            auto it = lower_bound(walls_x[x].begin(), walls_x[x].end(), y);
            if(it != walls_x[x].begin()){
                it = prev(it);
                adj[x][y].push_back({x, *it + 1, nearest_wall[x][y]});
            }
            // nearest wall to the right (>y)
            it = upper_bound(walls_x[x].begin(), walls_x[x].end(), y);
            if(it != walls_x[x].end()){
                adj[x][y].push_back({x, *it - 1, nearest_wall[x][y]});
            }
            // nearest wall down (<x)
            it = lower_bound(walls_y[y].begin(), walls_y[y].end(), x);
            if(it != walls_y[y].begin()){
                it = prev(it);
                adj[x][y].push_back({*it + 1, y, nearest_wall[x][y]});
            }
            // nearest wall up (>x)
            it = upper_bound(walls_y[y].begin(), walls_y[y].end(), x);
            if(it != walls_y[y].end()){
                adj[x][y].push_back({*it - 1, y, nearest_wall[x][y]});
            }
        }
    }
    using a3 = array<int,3>;
    priority_queue<a3,vector<a3>,greater<a3>>pq;
    pq.push({0,stx,sty});
    int dist[N][N];
    memset(dist,0xf3f3f,sizeof(dist));
    dist[stx][sty]=0;
    while(!pq.empty()){
        int x = get<1>(pq.top());
        int y = get<2>(pq.top());
        int d = get<0>(pq.top());
        pq.pop();
        if(dist[x][y]!=d)continue;
        for(auto&edge:adj[x][y]){
            int nx=edge[0],ny=edge[1];
            if(d + edge[2] < dist[nx][ny]){
                dist[nx][ny]=d+edge[2];
                pq.push({dist[nx][ny],nx,ny});
            }
        }
    }
    cout<<dist[endx][endy];
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:113:26: warning: 'endy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     cout<<dist[endx][endy];
      |                          ^
portals.cpp:113:26: warning: 'endx' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:98:19: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     dist[stx][sty]=0;
      |     ~~~~~~~~~~~~~~^~
portals.cpp:98:19: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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