이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |