제출 #943220

#제출 시각아이디문제언어결과실행 시간메모리
943220WongYiKai포탈들 (BOI14_portals)C++14
0 / 100
1 ms596 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll r,c; ll a(ll i, ll j) { return (i)*(c+2)+j; } pair<ll,ll> ra(ll x) { return {(x)/(c+2),(x)%(c+2)}; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> r >> c; if (r*c>100) return 0; ll grid[r+5][c+5]; ll s,e; memset(grid,0,sizeof(grid)); for (int i=1;i<=r;i++){ string temp; cin >> temp; for (int j=1;j<=c;j++){ if (temp[j-1]=='.') grid[i][j] = 1; else if (temp[j-1]=='#') grid[i][j] = 0; else if (temp[j-1]=='C') { grid[i][j] = 1; e = a(i,j); } else{ grid[i][j] = 1; s = a(i,j); } } } ll visited[r*c*2]; queue<pair<ll,ll>> bfs; memset(visited,0,sizeof(visited)); for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ if (grid[i][j]==0) continue; ll check=0; if (grid[i-1][j]==0) check=1; else if (grid[i+1][j]==0) check=1; else if (grid[i][j-1]==0) check=1; else if (grid[i][j+1]==0) check=1; if (check==0) continue; bfs.push({a(i,j),0}); visited[a(i,j)]=1; } } ll dist[r*c*2]; memset(dist,-1,sizeof(dist)); while (!bfs.empty()){ ll x = bfs.front().first; ll rnk = bfs.front().second; dist[x] = rnk; bfs.pop(); ll item; pair<ll,ll> temp; item=x-1; if (visited[item]==0){ temp = ra(item); if (grid[temp.first][temp.second]==1){ visited[item] = 1; bfs.push({item,rnk+1}); } } item=x+1; if (visited[item]==0){ temp = ra(item); if (grid[temp.first][temp.second]==1){ visited[item] = 1; bfs.push({item,rnk+1}); } } item=x-c-2; if (visited[item]==0){ temp = ra(item); if (grid[temp.first][temp.second]==1){ visited[item] = 1; bfs.push({item,rnk+1}); } } item=x+c+2; if (visited[item]==0){ temp = ra(item); if (grid[temp.first][temp.second]==1){ visited[item] = 1; bfs.push({item,rnk+1}); } } } /* for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ cout << dist[a(i,j)] << " "; } cout << "\n"; } */ ll left[r*c*2],right[r*c*2],up[r*c*2],down[r*c*2]; for (int j=1;j<=c;j++) up[a(0,j)] = a(0,j); for (int i=1;i<=r;i++){ if (grid[i][1]==0) { left[a(i,1)]=a(i,1); up[a(i,1)]=a(i,1); } else { left[a(i,1)]=a(i,0); up[a(i,1)] = up[a(i-1,1)]; } for (int j=2;j<=c;j++){ if (grid[i][j]==0) { left[a(i,j)] = a(i,j); up[a(i,j)] = a(i,j); } else { left[a(i,j)] = left[a(i,j-1)]; up[a(i,j)] = up[a(i-1,j)]; } } } //right down for (int j=1;j<=c;j++) down[a(r+1,j)] = a(r+1,j); for (int i=r;i>=1;i--){ if (grid[i][c]==0) { right[a(i,c)]=a(i,c); down[a(i,c)]=a(i,c); } else { right[a(i,c)]=a(i,c+1); down[a(i,c)] = down[a(i+1,c)]; } for (int j=c-1;j>=1;j--){ if (grid[i][j]==0) { right[a(i,j)] = a(i,j); down[a(i,j)] = a(i,j); } else { right[a(i,j)] = right[a(i,j+1)]; down[a(i,j)] = down[a(i+1,j)]; } } } /* cout << "left\n"; for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ cout << ra(left[a(i,j)]).first << "," << ra(left[a(i,j)]).second << " "; } cout << "\n"; } cout << "right\n"; for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ cout << ra(right[a(i,j)]).first << "," << ra(right[a(i,j)]).second << " "; } cout << "\n"; } cout << "down\n"; for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ cout << ra(down[a(i,j)]).first << "," << ra(down[a(i,j)]).second << " "; } cout << "\n"; } cout << "up\n"; for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ cout << ra(up[a(i,j)]).first << "," << ra(up[a(i,j)]).second << " "; } cout << "\n"; } */ vector<pair<ll,ll>> adj[r*c*2]; for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ if (grid[i][j]==0) continue; ll x = a(i,j); ll item; pair<ll,ll> temp; item=x-1; temp = ra(item); if (grid[temp.first][temp.second]==1){ adj[x].push_back({item,1}); } item=x+1; temp = ra(item); if (grid[temp.first][temp.second]==1){ adj[x].push_back({item,1}); } item=x-c-2; temp = ra(item); if (grid[temp.first][temp.second]==1){ adj[x].push_back({item,1}); } item=x+c+2; temp = ra(item); if (grid[temp.first][temp.second]==1){ adj[x].push_back({item,1}); } adj[x].push_back({left[x]+1,dist[x]+1}); adj[x].push_back({down[x]-c-2,dist[x]+1}); adj[x].push_back({up[x]+c+2,dist[x]+1}); adj[x].push_back({right[x]-1,dist[x]+1}); } } /* for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ cout << i << "," << j << ": "; for (auto item:adj[a(i,j)]){ cout << ra(item.first).first << "," << ra(item.first).second << "," << item.second << " "; } cout << "\n"; } } */ ll dis[r*c*2]; priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq; memset(dis,-1,sizeof(dis)); dis[s]=0; pq.push({0,s}); while (!pq.empty()) { pair<ll,ll> cur = pq.top(); pq.pop(); ll x = cur.second, d = cur.first; if (d>dis[x]) continue; for (vector<pair<ll,ll>>::iterator it=adj[x].begin();it!=adj[x].end();++it){ ll nx = it->first, nd = d+it->second; if (dis[nx]!=-1 && dis[nx]<=nd) continue; dis[nx] = nd; pq.push({nd,nx}); } } /* for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ cout << dis[a(i,j)] << " "; } cout << "\n"; } */ cout << dis[e]; //cout << "a"; }

컴파일 시 표준 에러 (stderr) 메시지

portals.cpp: In function 'int main()':
portals.cpp:251:15: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
  251 |  cout << dis[e];
      |               ^
#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...