이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}
}
# | 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... |