Submission #941081

#TimeUsernameProblemLanguageResultExecution timeMemory
941081KaleemRazaSyedPortals (BOI14_portals)C++17
20 / 100
28 ms69980 KiB
#include<iostream> #include<vector> #include<queue> using namespace std; const int N = 1e3 + 5; char grid[N][N]; int left_[N][N], right_[N][N], up[N][N], down[N][N]; vector<int> G[N * N], port[N * N]; int dist[N * N]; int r, c, m; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; bool valid(int x, int y) { return (x > 0 && y > 0 && x <= r && y <= c && grid[x][y] != '#'); } void bfs(int v, int u) { for(int i = 0; i < N * N; i++) dist[i] = N * N + 10; queue<int> q; vector<int> portals; q.push(v); dist[v] = 0; while(q.size()) { int w = q.front(); q.pop(); bool hold = false; for(int i : port[w]) { portals.push_back(i); hold |= (w == i); } for(int k : G[w]) { if(dist[w] + 1 < dist[k]) { dist[k] = dist[w] + 1; q.push(k); } } if(hold) { for(int i : portals) if(dist[w] + 1 < dist[i]) { dist[i] = dist[w] + 1; q.push(i); } portals.clear(); } } //for(int i = 1; i <= r; i++) //for(int j = 1; j <= c; j++) // cout << dist[i * m + j] << " \n"[j == c]; cout << dist[u] << endl; } int main() { cin >> r >> c; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) cin >> grid[i][j]; m = c + 2; for(int i = 1; i <= r; i ++) for(int j = 1; j <= c; j ++) { if(grid[i][j] == '#') continue; int ij = i * m + j; for(int n = 0; n < 4; n++) { int ni = i + dx[n], nj = j + dy[n]; int nij = ni * m + nj; if(valid(ni, nj)) G[ij].push_back(nij); } } for(int i = 1; i <= r; i ++) { int p = 0; for(int j = 1; j <= c; j++) { if(grid[i][j] == '#') p = j; left_[i][j] = p; } int n = c + 1; for(int j = c; j >= 1; j--) { if(grid[i][j] == '#') n = j; right_[i][j] = n; } } for(int j = 1; j <= c; j ++) { int p = 0; for(int i = 1; i <= r; i ++) { if(grid[i][j] == '#') p = i; up[i][j] = p; } int n = r + 1; for(int i = r; i >= 1; i--) { if(grid[i][j] == '#') n = i; down[i][j] = n; } } for(int i = 1; i <= r; i ++) for(int j = 1; j <= c; j++) { if(grid[i][j] == '#') continue; int idx = i * m + j; int idx1 = i * m + left_[i][j] + 1; int idx2 = i * m + right_[i][j] - 1; int idx3 = (up[i][j] + 1) * m + j; int idx4 = (down[i][j] - 1) * m + j; port[idx].push_back(idx1); port[idx].push_back(idx2); port[idx].push_back(idx3); port[idx].push_back(idx4); } int v, u; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) if(grid[i][j] == 'S') v = i * m + j; else if(grid[i][j] == 'C') u = i * m + j; bfs(v, u); return 0; }

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:156:6: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
  156 |   bfs(v, u);
      |   ~~~^~~~~~
portals.cpp:156:6: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
#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...