This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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,0xf3f,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 = tuple<short,short,short>;
priority_queue<a3,vector<a3>,greater<a3>>pq;
pq.push({0,stx,sty});
short dist[N][N];
memset(dist,0xf3f,sizeof(dist));
dist[stx][sty]=0;
while(!pq.empty()){
short x = get<1>(pq.top());
short y = get<2>(pq.top());
short d = get<0>(pq.top());
pq.pop();
if(dist[x][y]!=d)continue;
for(auto&edge:adj[x][y]){
short 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:98:19: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]
98 | dist[stx][sty]=0;
| ~~~~~~~~~~~~~~^~
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]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |