Submission #941118

#TimeUsernameProblemLanguageResultExecution timeMemory
941118Ghulam_JunaidPortals (BOI14_portals)C++17
100 / 100
279 ms51684 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 10; const int inf = 1e9 + 10; int n, m, sx, sy, ex, ey, dist[N][N]; char mat[N][N]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; // U R D L vector<pair<int, int>> walls; pair<int, int> max_move[N][N][4]; int wall_dist[N][N]; bool valid(int x, int y){ return (x >= 0 and x < n and y >= 0 and y < m and mat[x][y] != '#'); } void bfs(){ for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) wall_dist[i][j] = min(min(i + 1, j + 1), min(n - i, m - j)); queue<pair<int, int>> q; for (auto [x, y] : walls){ wall_dist[x][y] = 0; q.push({x, y}); } while (!q.empty()){ auto p = q.front(); q.pop(); int x = p.first; int y = p.second; for (int d = 0; d < 4; d ++){ int nx = x + dx[d]; int ny = y + dy[d]; if (valid(nx, ny) and wall_dist[nx][ny] > wall_dist[x][y] + 1){ wall_dist[nx][ny] = wall_dist[x][y] + 1; q.push({nx, ny}); } } } } void dijkstra(){ for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) dist[i][j] = inf; dist[sx][sy] = 0; set<pair<int, pair<int, int>>> st; st.insert({0, {sx, sy}}); while (!st.empty()){ auto X = *st.begin(); st.erase(st.begin()); int cur = X.first; auto p = X.second; int x = p.first; int y = p.second; for (int d = 0; d < 4; d ++){ int nx = x + dx[d]; int ny = y + dy[d]; if (valid(nx, ny) and dist[nx][ny] > dist[x][y] + 1){ st.erase({dist[nx][ny], {nx, ny}}); dist[nx][ny] = dist[x][y] + 1; st.insert({dist[nx][ny], {nx, ny}}); } p = max_move[x][y][d]; nx = p.first; ny = p.second; if (dist[nx][ny] > dist[x][y] + wall_dist[x][y]){ st.erase({dist[nx][ny], {nx, ny}}); dist[nx][ny] = dist[x][y] + wall_dist[x][y]; st.insert({dist[nx][ny], {nx, ny}}); } } } } int main(){ cin >> n >> m; for (int i = 0; i < n; i ++){ for (int j = 0; j < m; j ++){ cin >> mat[i][j]; if (mat[i][j] == 'S') sx = i, sy = j; if (mat[i][j] == 'C') ex = i, ey = j; if (mat[i][j] == '#') walls.push_back({i, j}); } } bfs(); for (int i = 0; i < n; i ++){ for (int j = 0; j < m; j ++){ if (mat[i][j] == '#') continue; if (valid(i - 1, j)) max_move[i][j][0] = max_move[i - 1][j][0]; else max_move[i][j][0] = {i, j}; if (valid(i, j - 1)) max_move[i][j][3] = max_move[i][j - 1][3]; else max_move[i][j][3] = {i, j}; } } for (int i = n - 1; i >= 0; i --){ for (int j = m - 1; j >= 0; j --){ if (mat[i][j] == '#') continue; if (valid(i + 1, j)) max_move[i][j][2] = max_move[i + 1][j][2]; else max_move[i][j][2] = {i, j}; if (valid(i, j + 1)) max_move[i][j][1] = max_move[i][j + 1][1]; else max_move[i][j][1] = {i, j}; } } dijkstra(); cout << dist[ex][ey] << endl; }

Compilation message (stderr)

portals.cpp: In function 'void dijkstra()':
portals.cpp:65:13: warning: unused variable 'cur' [-Wunused-variable]
   65 |         int cur = X.first;
      |             ^~~
#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...