제출 #466814

#제출 시각아이디문제언어결과실행 시간메모리
466814M4mou포탈들 (BOI14_portals)C++17
0 / 100
1 ms1356 KiB
#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 <= n; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...