# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
41145 |
2018-02-13T05:57:42 Z |
14kg |
Portals (BOI14_portals) |
C++11 |
|
1000 ms |
88452 KB |
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#define N 1001
#define INF 1000000000
using namespace std;
typedef pair<int,pair<int,int> > pip;
int n, m, board[N][N], go[N][N], d[N][N];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
bool go_check[N][N], check[N][N];
pair<int,int> S, E;
vector<pair<int,int> > p[N][N];
queue<int> Q;
priority_queue<pip,vector<pip>,greater<pip> > PQ;
void bfs_go(){
int ty, tx, yy, xx;
bool w_check;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
w_check=false;
for(int s=0; s<4; s++){
ty=i+dy[s], tx=j+dx[s];
if(ty<1 || ty>n || tx<1 || tx>m) w_check=true;
else if(board[ty][tx]) w_check=true;
}
if(w_check){
go_check[i][j]=true, Q.push(i), Q.push(j);
}
}
while(!Q.empty()){
yy=Q.front(), Q.pop();
xx=Q.front(), Q.pop();
for(int i=0; i<4; i++){
ty=yy+dy[i], tx=xx+dx[i];
if(1<=ty && ty<=n && 1<=tx && tx<=m && go_check[ty][tx]==false && board[ty][tx]==0){
go[ty][tx]=go[yy][xx]+1, go_check[ty][tx]=true;
Q.push(ty), Q.push(tx);
}
}
}
}
void Push(){
pair<int,int> temp;
for(int i=1; i<=n; i++){
temp={i,1};
for(int j=1; j<=m; j++){
if(board[i][j]) temp={i,j+1};
else p[i][j].push_back(temp);
}
}
for(int i=1; i<=n; i++){
temp={i,m};
for(int j=m; j>=1; j--){
if(board[i][j]) temp={i,j-1};
else p[i][j].push_back(temp);
}
}
for(int j=1; j<=m; j++){
temp={1,j};
for(int i=1; i<=n; i++){
if(board[i][j]) temp={i+1,j};
else p[i][j].push_back(temp);
}
}
for(int j=1; j<=m; j++){
temp={n,j};
for(int i=n; i>=1; i--){
if(board[i][j]) temp={i-1,j};
else p[i][j].push_back(temp);
}
}
}
int main(){
int yy, xx, ty, tx;
char in[1005];
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++){
scanf("%s",in+1);
for(int j=1; j<=m; j++)
if(in[j]=='#') board[i][j]=1;
else if(in[j]=='S') S={i,j};
else if(in[j]=='C') E={i,j};
}
bfs_go(), Push();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) d[i][j]=INF;
PQ.push({0,{S.first,S.second}}), d[S.first][S.second]=0;
while(!PQ.empty()){
yy=PQ.top().second.first, xx=PQ.top().second.second, PQ.pop();
if(check[yy][xx]) continue;
check[yy][xx]=true;
for(int i=0; i<4; i++){
ty=yy+dy[i], tx=xx+dx[i];
if(1<=ty && ty<=n && 1<=tx && tx<=m && d[ty][tx]>d[yy][xx]+1 && board[ty][tx]==0){
d[ty][tx]=d[yy][xx]+1;
PQ.push({d[ty][tx],{ty,tx}});
}
}
for(vector<pair<int,int> >::iterator it=p[yy][xx].begin(); it!=p[yy][xx].end(); it++){
ty=it->first, tx=it->second;
if(d[ty][tx]>d[yy][xx]+go[yy][xx]+1){
d[ty][tx]=d[yy][xx]+go[yy][xx]+1;
PQ.push({d[ty][tx],{ty,tx}});
}
}
}
printf("%d",d[E.first][E.second]);
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:85:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
^
portals.cpp:87:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",in+1);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
23928 KB |
Output is correct |
2 |
Correct |
20 ms |
23928 KB |
Output is correct |
3 |
Correct |
24 ms |
23960 KB |
Output is correct |
4 |
Correct |
20 ms |
24108 KB |
Output is correct |
5 |
Correct |
20 ms |
24168 KB |
Output is correct |
6 |
Correct |
22 ms |
24220 KB |
Output is correct |
7 |
Correct |
21 ms |
24232 KB |
Output is correct |
8 |
Correct |
20 ms |
24252 KB |
Output is correct |
9 |
Correct |
21 ms |
24252 KB |
Output is correct |
10 |
Correct |
21 ms |
24252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
24252 KB |
Output is correct |
2 |
Correct |
21 ms |
24264 KB |
Output is correct |
3 |
Correct |
19 ms |
24264 KB |
Output is correct |
4 |
Correct |
21 ms |
24264 KB |
Output is correct |
5 |
Correct |
21 ms |
24264 KB |
Output is correct |
6 |
Correct |
21 ms |
24272 KB |
Output is correct |
7 |
Correct |
21 ms |
24272 KB |
Output is correct |
8 |
Correct |
21 ms |
24324 KB |
Output is correct |
9 |
Correct |
22 ms |
24968 KB |
Output is correct |
10 |
Correct |
22 ms |
24972 KB |
Output is correct |
11 |
Correct |
21 ms |
24972 KB |
Output is correct |
12 |
Correct |
22 ms |
24972 KB |
Output is correct |
13 |
Correct |
21 ms |
25008 KB |
Output is correct |
14 |
Correct |
20 ms |
25008 KB |
Output is correct |
15 |
Correct |
22 ms |
25008 KB |
Output is correct |
16 |
Correct |
26 ms |
25008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
25008 KB |
Output is correct |
2 |
Correct |
20 ms |
25008 KB |
Output is correct |
3 |
Correct |
20 ms |
25008 KB |
Output is correct |
4 |
Correct |
21 ms |
25008 KB |
Output is correct |
5 |
Correct |
34 ms |
27436 KB |
Output is correct |
6 |
Correct |
39 ms |
27476 KB |
Output is correct |
7 |
Correct |
38 ms |
27532 KB |
Output is correct |
8 |
Correct |
32 ms |
27652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
27652 KB |
Output is correct |
2 |
Correct |
21 ms |
27652 KB |
Output is correct |
3 |
Correct |
20 ms |
27652 KB |
Output is correct |
4 |
Correct |
19 ms |
27652 KB |
Output is correct |
5 |
Correct |
20 ms |
27652 KB |
Output is correct |
6 |
Correct |
21 ms |
27652 KB |
Output is correct |
7 |
Correct |
25 ms |
27652 KB |
Output is correct |
8 |
Correct |
21 ms |
27652 KB |
Output is correct |
9 |
Correct |
22 ms |
27652 KB |
Output is correct |
10 |
Correct |
22 ms |
27652 KB |
Output is correct |
11 |
Correct |
22 ms |
27652 KB |
Output is correct |
12 |
Correct |
22 ms |
27652 KB |
Output is correct |
13 |
Correct |
21 ms |
27652 KB |
Output is correct |
14 |
Correct |
35 ms |
27652 KB |
Output is correct |
15 |
Correct |
37 ms |
27732 KB |
Output is correct |
16 |
Correct |
39 ms |
27872 KB |
Output is correct |
17 |
Correct |
38 ms |
28592 KB |
Output is correct |
18 |
Correct |
42 ms |
28888 KB |
Output is correct |
19 |
Correct |
42 ms |
28888 KB |
Output is correct |
20 |
Correct |
42 ms |
29352 KB |
Output is correct |
21 |
Correct |
39 ms |
29352 KB |
Output is correct |
22 |
Correct |
35 ms |
29352 KB |
Output is correct |
23 |
Correct |
37 ms |
29352 KB |
Output is correct |
24 |
Correct |
42 ms |
29528 KB |
Output is correct |
25 |
Correct |
23 ms |
29528 KB |
Output is correct |
26 |
Correct |
22 ms |
29528 KB |
Output is correct |
27 |
Correct |
21 ms |
29528 KB |
Output is correct |
28 |
Correct |
33 ms |
29528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
29528 KB |
Output is correct |
2 |
Correct |
20 ms |
29528 KB |
Output is correct |
3 |
Correct |
19 ms |
29528 KB |
Output is correct |
4 |
Correct |
21 ms |
29528 KB |
Output is correct |
5 |
Correct |
20 ms |
29528 KB |
Output is correct |
6 |
Correct |
20 ms |
29528 KB |
Output is correct |
7 |
Correct |
20 ms |
29528 KB |
Output is correct |
8 |
Correct |
20 ms |
29528 KB |
Output is correct |
9 |
Correct |
22 ms |
29528 KB |
Output is correct |
10 |
Correct |
22 ms |
29528 KB |
Output is correct |
11 |
Correct |
22 ms |
29528 KB |
Output is correct |
12 |
Correct |
22 ms |
29528 KB |
Output is correct |
13 |
Correct |
22 ms |
29528 KB |
Output is correct |
14 |
Correct |
35 ms |
29528 KB |
Output is correct |
15 |
Correct |
36 ms |
29528 KB |
Output is correct |
16 |
Correct |
40 ms |
29528 KB |
Output is correct |
17 |
Correct |
37 ms |
29528 KB |
Output is correct |
18 |
Correct |
40 ms |
29528 KB |
Output is correct |
19 |
Correct |
42 ms |
29528 KB |
Output is correct |
20 |
Correct |
48 ms |
30000 KB |
Output is correct |
21 |
Correct |
38 ms |
30000 KB |
Output is correct |
22 |
Correct |
35 ms |
30000 KB |
Output is correct |
23 |
Correct |
36 ms |
30000 KB |
Output is correct |
24 |
Correct |
719 ms |
74696 KB |
Output is correct |
25 |
Execution timed out |
1033 ms |
88452 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |