제출 #159157

#제출 시각아이디문제언어결과실행 시간메모리
159157TadijaSebezDangerous Skating (JOI16_skating)C++11
100 / 100
1033 ms210364 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back const int inf=1e9+7; const int N=1050; const int H=N*N*4; int n,m; int ID(int x, int y){ return (x-1)*m+y;} vector<pair<int,int>> E[H]; int dist[H]; bool was[H]; char base[N][N]; int main() { scanf("%i %i",&n,&m); for(int i=1;i<=n;i++) scanf("%s",base[i]+1); for(int i=1;i<=n;i++) { for(int j=1,k=1;j<=m;j++) { if(base[i][j]=='#') k=j+1; else E[ID(i,j)].pb({ID(i,k),1}); } for(int j=m,k=m;j>=1;j--) { if(base[i][j]=='#') k=j-1; else E[ID(i,j)].pb({ID(i,k),1}); } } for(int i=1;i<=m;i++) { for(int j=1,k=1;j<=n;j++) { if(base[j][i]=='#') k=j+1; else E[ID(j,i)].pb({ID(k,i),1}); } for(int j=n,k=n;j>=1;j--) { if(base[j][i]=='#') k=j-1; else E[ID(j,i)].pb({ID(k,i),1}); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(base[i][j]=='.') { if(base[i][j-1]=='.') E[ID(i,j)].pb({ID(i,j-1),2}); if(base[i][j+1]=='.') E[ID(i,j)].pb({ID(i,j+1),2}); if(base[i-1][j]=='.') E[ID(i,j)].pb({ID(i-1,j),2}); if(base[i+1][j]=='.') E[ID(i,j)].pb({ID(i+1,j),2}); } int x,y,a,b; scanf("%i %i %i %i",&x,&y,&a,&b); if(x==a && y==b) return 0*printf("0\n"); for(int i=0;i<H;i++) dist[i]=inf; queue<pair<int,int>> q[2]; q[0].push({ID(x,y),0}); dist[ID(x,y)]=0; while(q[0].size()+q[1].size()) { int u,d; if(q[0].empty() || (q[1].size() && q[1].front().second<q[0].front().second)) { tie(u,d)=q[1].front(); q[1].pop(); } else { tie(u,d)=q[0].front(); q[0].pop(); } if(dist[u]!=d) continue; for(auto e:E[u]) { int v,w;tie(v,w)=e; if(dist[v]>dist[u]+w) { dist[v]=dist[u]+w; q[w-1].push({v,dist[v]}); } } } int ans=dist[ID(a,b)]; if(ans==inf) printf("-1\n"); else printf("%i\n",ans); return 0; }

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

skating.cpp: In function 'int main()':
skating.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
skating.cpp:16:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
                        ~~~~~^~~~~~~~~~~~~~~~
skating.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&x,&y,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...