#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");
// }
}
Compilation message
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 |
| 1 |
Correct |
0 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
0 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
13024 KB |
Output is correct |
| 2 |
Correct |
4 ms |
13024 KB |
Output is correct |
| 3 |
Correct |
7 ms |
13024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
13164 KB |
Output is correct |
| 2 |
Correct |
8 ms |
13156 KB |
Output is correct |
| 3 |
Correct |
9 ms |
13024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
13552 KB |
Output is correct |
| 2 |
Correct |
32 ms |
13420 KB |
Output is correct |
| 3 |
Correct |
16 ms |
13288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
13824 KB |
Output is correct |
| 2 |
Correct |
22 ms |
13816 KB |
Output is correct |
| 3 |
Correct |
27 ms |
13552 KB |
Output is correct |
| 4 |
Correct |
30 ms |
13420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
13844 KB |
Output is correct |
| 2 |
Correct |
28 ms |
13948 KB |
Output is correct |
| 3 |
Correct |
70 ms |
13948 KB |
Output is correct |
| 4 |
Correct |
49 ms |
13948 KB |
Output is correct |
