이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
#include<queue>
#define inf 2e9
using namespace std;
int In[505][505],Wall[505][505],Sp[505][505];
deque< pair<int,int> > Q;
priority_queue< pair<int,pair<int,int> > > Pq;
struct xx{
pair<int,int> up,dn,lf,ri;
}Por[505][505];
pair<int,pair<int,int> > make_triple(int a,int b,int c){
pair<int,pair<int,int> > temp;
temp.first=a;
temp.second.first=b;
temp.second.second=c;
return temp;
}
void Op(int x,int y,int tempx,int tempy,int tempdis){
if(In[tempx][tempy]!='#'&&Sp[tempx][tempy]>Sp[x][y]+tempdis){
Sp[tempx][tempy]=Sp[x][y]+tempdis;
Pq.push(make_triple(-Sp[tempx][tempy],tempx,tempy));
}
}
main(){
int n,m;
pair<int,int> ed;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf(" %c",&In[i][j]);
if(In[i][j]=='#')
Q.push_back(make_pair(i,j));
else
Wall[i][j]=inf;
if(In[i][j]=='C')
Pq.push(make_triple(0,i,j));
else
Sp[i][j]=inf;
if(In[i][j]=='F')
ed=make_pair(i,j);
}
}
for(int i=1;i<=n;i++){
int temp1=1;
for(int j=1;j<=m;j++){
if(In[i][j]=='#'){
temp1=j+1;
continue;
}
Por[i][j].lf=make_pair(i,temp1);
}
int temp2=m;
for(int j=m;j>=1;j--){
if(In[i][j]=='#'){
temp2=j-1;
continue;
}
Por[i][j].ri=make_pair(i,temp2);
}
}
for(int j=1;j<=m;j++){
int temp1=1;
for(int i=1;i<=n;i++){
if(In[i][j]=='#'){
temp1=i+1;
continue;
}
Por[i][j].up=make_pair(temp1,j);
}
int temp2=n;
for(int i=n;i>=1;i--){
if(In[i][j]=='#'){
temp2=i-1;
continue;
}
Por[i][j].dn=make_pair(temp2,j);
}
}
while(!Q.empty()){
int x=Q.front().first;
int y=Q.front().second;
Q.pop_front();
if(Wall[x+1][y]==inf){
Wall[x+1][y]=Wall[x][y]+1;
Q.push_back(make_pair(x+1,y));
}
if(Wall[x-1][y]==inf){
Wall[x-1][y]=Wall[x][y]+1;
Q.push_back(make_pair(x-1,y));
}
if(Wall[x][y+1]==inf){
Wall[x][y+1]=Wall[x][y]+1;
Q.push_back(make_pair(x,y+1));
}
if(Wall[x][y-1]==inf){
Wall[x][y-1]=Wall[x][y]+1;
Q.push_back(make_pair(x,y-1));
}
}
int tempx,tempy,tempdis;
while(!Pq.empty()){
int dis=-Pq.top().first;
int x=Pq.top().second.first;
int y=Pq.top().second.second;
Pq.pop();
if(dis!=Sp[x][y])
continue;
Op(x,y,x+1,y,1);
Op(x,y,x-1,y,1);
Op(x,y,x,y+1,1);
Op(x,y,x,y-1,1);
Op(x,y,Por[x][y].up.first,Por[x][y].up.second,Wall[x][y]);
Op(x,y,Por[x][y].dn.first,Por[x][y].dn.second,Wall[x][y]);
Op(x,y,Por[x][y].lf.first,Por[x][y].lf.second,Wall[x][y]);
Op(x,y,Por[x][y].ri.first,Por[x][y].ri.second,Wall[x][y]);
}
if(Sp[ed.first][ed.second]!=inf)
printf("%d",Sp[ed.first][ed.second]);
else
printf("nemoguce");
// printf("\n\n");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// if(Sp[i][j]==inf)
// printf("- ");
// else printf("%d ",Sp[i][j]);
// }
// printf("\n");
// }
// printf("\n\n");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++)
// printf("%d ",Wall[i][j]);
// printf("\n");
// }
}
컴파일 시 표준 에러 (stderr) 메시지
portal.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
portal.cpp: In function 'int main()':
portal.cpp:35:34: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat=]
scanf(" %c",&In[i][j]);
^
portal.cpp:105:9: warning: unused variable 'tempx' [-Wunused-variable]
int tempx,tempy,tempdis;
^
portal.cpp:105:15: warning: unused variable 'tempy' [-Wunused-variable]
int tempx,tempy,tempdis;
^
portal.cpp:105:21: warning: unused variable 'tempdis' [-Wunused-variable]
int tempx,tempy,tempdis;
^
portal.cpp:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
portal.cpp:35:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&In[i][j]);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |