제출 #26204

#제출 시각아이디문제언어결과실행 시간메모리
26204samir_droubi포탈들 (BOI14_portals)C++14
70 / 100
1000 ms145192 KiB
#pragma optimize("O3") #include <bits/stdc++.h> using namespace std; const int mxn=1005; int n,m; char g[mxn][mxn]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; bool check(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]!='#'; } int wall[mxn][mxn]; queue<pair<int,int> >q; void bfs() { while(!q.empty()) { int x=q.front().first; int y=q.front().second; q.pop(); for(int i=0;i<4;++i) { int xx=x+dx[i]; int yy=y+dy[i]; if(!check(xx,yy))continue; if(wall[xx][yy]>wall[x][y]+1) { wall[xx][yy]=wall[x][y]+1; q.push({xx,yy}); } } } } vector<pair<pair<int,int>,int> >adj[mxn][mxn];; int dist[mxn][mxn]; set<pair<int,pair<int,int> > >pq; void dijkstra(int x,int y) { dist[x][y]=0; pq.insert({0,{x,y}}); while(!pq.empty()) { pair<int,pair<int,int> > p=*pq.begin(); pq.erase(pq.begin()); int ds=p.first; int x=p.second.first; int y=p.second.second; for(int i=0;i<adj[x][y].size();++i) { int xx=adj[x][y][i].first.first; int yy=adj[x][y][i].first.second; int w=adj[x][y][i].second; if(dist[xx][yy]>ds+w) { dist[xx][yy]=ds+w; pq.insert({ds+w,{xx,yy}}); } } } } void clear() { for(int i=0;i<mxn;++i) for(int j=0;j<mxn;++j) { wall[i][j]=(1e9); dist[i][j]=(1e9); } } void up(int i,int j) { int x=i; while(x>=1&&g[x][j]!='#') { adj[x][j].push_back({{i,j},wall[x][j]}); --x; } } void down(int i,int j) { int x=i; while(x<=n&&g[x][j]!='#') { adj[x][j].push_back({{i,j},wall[x][j]}); ++x; } } void left(int i,int j) { int y=j; while(y>=1&&g[i][y]!='#') { adj[i][y].push_back({{i,j},wall[i][y]}); --y; } } void right(int i,int j) { int y=j; while(y<=m&&g[i][y]!='#') { adj[i][y].push_back({{i,j},wall[i][y]}); ++y; } } int main() { clear(); int sx,sy,ex,ey; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%s",&g[i]); g[i][m+1]='\0'; for(int j=m;j>=1;--j) { g[i][j]=g[i][j-1]; if(g[i][j]=='S') { sx=i; sy=j; } if(g[i][j]=='C') { ex=i; ey=j; } } } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { bool ok=false; for(int k=0;k<4;++k) { int x=i+dx[k]; int y=j+dy[k]; if(!check(x,y))ok=true; else adj[i][j].push_back({{x,y},1}); } if(ok) { wall[i][j]=1; q.push({i,j}); } } bfs(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { if(g[i][j]!='#')continue; right(i,j+1); left(i,j-1); up(i-1,j); down(i+1,j); } for(int i=1;i<=n;++i) { right(i,1); left(i,n); } for(int j=1;j<=m;++j) { down(1,j); up(m,j); } dijkstra(sx,sy); printf("%d\n",dist[ex][ey]); return 0; }

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

portals.cpp:1:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("O3")
 ^
portals.cpp: In function 'void dijkstra(int, int)':
portals.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<adj[x][y].size();++i)
                ^
portals.cpp: In function 'int main()':
portals.cpp:117:19: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1005]' [-Wformat=]
   scanf("%s",&g[i]);
                   ^
portals.cpp:114:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
portals.cpp:117:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",&g[i]);
                    ^
portals.cpp:175:8: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  printf("%d\n",dist[ex][ey]);
        ^
portals.cpp:175:8: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:174:17: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dijkstra(sx,sy);
                 ^
portals.cpp:174:17: warning: 'sx' 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...