# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
11210 |
2014-11-18T23:55:03 Z |
gs14004 |
Portals (BOI14_portals) |
C++ |
|
720 ms |
58792 KB |
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;
typedef pair<int,pi> edge;
char str[1005][1005];
int ply[1005][1005];
int pry[1005][1005];
int pux[1005][1005];
int pdx[1005][1005];
int r,c;
priority_queue<edge,vector<edge>,greater<edge> > pq;
int v[1005][1005];
void input(){
scanf("%d %d",&r,&c);
for (int i=0; i<r; i++) {
scanf("%s",str[i]);
for (int j=0; j<c; j++) {
if(str[i][j] == 'S'){
pq.push(edge(0,pi(i,j)));
}
}
}
}
void make_portal(){
for (int i=0; i<r; i++) {
int piv = 0;
for (int j=0; j<c; j++) {
if(str[i][j] == '#') piv = j+1;
pry[i][j] = piv;
}
}
for (int i=0; i<r; i++) {
int piv = c-1;
for (int j=c-1; j>=0; j--) {
if(str[i][j] == '#') piv = j-1;
ply[i][j] = piv;
}
}
for (int j=0; j<c; j++) {
int piv = 0;
for (int i=0; i<r; i++) {
if(str[i][j] == '#') piv = i+1;
pdx[i][j] = piv;
}
}
for (int j=0; j<c; j++) {
int piv = r-1;
for (int i=r-1; i>=0; i--) {
if(str[i][j] == '#') piv = i-1;
pux[i][j] = piv;
}
}
}
inline void push(int x, int y, int d){
if(x < 0 || x >= r || y < 0 || y >= c) return;
if(v[x][y]) return;
if(str[x][y] == '#') return;
pq.push(edge(d,pi(x,y)));
}
int main(){
input();
make_portal();
while (!pq.empty()) {
edge c = pq.top();
pq.pop();
int x = c.second.first;
int y = c.second.second;
int d = c.first;
if(v[x][y]) continue;
if(str[x][y] == 'C'){
printf("%d",d);
return 0;
}
v[x][y] = 1;
push(x-1,y,d+1);
push(x,y-1,d+1);
push(x+1,y,d+1);
push(x,y+1,d+1);
// get closest portal position
int dist = min(abs(ply[x][y] - y),abs(y - pry[x][y]));
dist = min(dist,min(abs(pux[x][y] - x),abs(pdx[x][y] - x)));
// closest portals?
push(x,ply[x][y],d+dist+1);
push(x,pry[x][y],d+dist+1);
push(pux[x][y],y,d+dist+1);
push(pdx[x][y],y,d+dist+1);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
21924 KB |
Output is correct |
2 |
Correct |
0 ms |
21924 KB |
Output is correct |
3 |
Correct |
0 ms |
21924 KB |
Output is correct |
4 |
Correct |
0 ms |
21924 KB |
Output is correct |
5 |
Correct |
0 ms |
21924 KB |
Output is correct |
6 |
Correct |
0 ms |
21924 KB |
Output is correct |
7 |
Correct |
0 ms |
21924 KB |
Output is correct |
8 |
Correct |
0 ms |
21924 KB |
Output is correct |
9 |
Correct |
0 ms |
21924 KB |
Output is correct |
10 |
Correct |
0 ms |
21924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
21924 KB |
Output is correct |
2 |
Correct |
0 ms |
21924 KB |
Output is correct |
3 |
Correct |
0 ms |
21924 KB |
Output is correct |
4 |
Correct |
0 ms |
21924 KB |
Output is correct |
5 |
Correct |
0 ms |
21924 KB |
Output is correct |
6 |
Correct |
0 ms |
21924 KB |
Output is correct |
7 |
Correct |
0 ms |
21924 KB |
Output is correct |
8 |
Correct |
0 ms |
21924 KB |
Output is correct |
9 |
Correct |
0 ms |
21924 KB |
Output is correct |
10 |
Correct |
0 ms |
22116 KB |
Output is correct |
11 |
Correct |
0 ms |
21924 KB |
Output is correct |
12 |
Correct |
0 ms |
21924 KB |
Output is correct |
13 |
Correct |
0 ms |
21924 KB |
Output is correct |
14 |
Correct |
0 ms |
21924 KB |
Output is correct |
15 |
Correct |
0 ms |
21924 KB |
Output is correct |
16 |
Correct |
0 ms |
21924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
21924 KB |
Output is correct |
2 |
Correct |
0 ms |
21924 KB |
Output is correct |
3 |
Correct |
0 ms |
21924 KB |
Output is correct |
4 |
Correct |
0 ms |
21924 KB |
Output is correct |
5 |
Correct |
4 ms |
21924 KB |
Output is correct |
6 |
Correct |
8 ms |
21924 KB |
Output is correct |
7 |
Correct |
12 ms |
21924 KB |
Output is correct |
8 |
Correct |
0 ms |
21924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
21924 KB |
Output is correct |
2 |
Correct |
0 ms |
21924 KB |
Output is correct |
3 |
Correct |
0 ms |
21924 KB |
Output is correct |
4 |
Correct |
0 ms |
21924 KB |
Output is correct |
5 |
Correct |
0 ms |
21924 KB |
Output is correct |
6 |
Correct |
0 ms |
21924 KB |
Output is correct |
7 |
Correct |
0 ms |
21924 KB |
Output is correct |
8 |
Correct |
0 ms |
21924 KB |
Output is correct |
9 |
Correct |
0 ms |
21924 KB |
Output is correct |
10 |
Correct |
0 ms |
22116 KB |
Output is correct |
11 |
Correct |
0 ms |
21924 KB |
Output is correct |
12 |
Correct |
0 ms |
21924 KB |
Output is correct |
13 |
Correct |
0 ms |
21924 KB |
Output is correct |
14 |
Correct |
8 ms |
21924 KB |
Output is correct |
15 |
Correct |
4 ms |
21924 KB |
Output is correct |
16 |
Correct |
8 ms |
21924 KB |
Output is correct |
17 |
Correct |
8 ms |
21924 KB |
Output is correct |
18 |
Correct |
12 ms |
21924 KB |
Output is correct |
19 |
Correct |
0 ms |
22116 KB |
Output is correct |
20 |
Correct |
16 ms |
24232 KB |
Output is correct |
21 |
Correct |
12 ms |
21924 KB |
Output is correct |
22 |
Correct |
0 ms |
21924 KB |
Output is correct |
23 |
Correct |
8 ms |
21924 KB |
Output is correct |
24 |
Correct |
8 ms |
21924 KB |
Output is correct |
25 |
Correct |
0 ms |
21924 KB |
Output is correct |
26 |
Correct |
0 ms |
21924 KB |
Output is correct |
27 |
Correct |
0 ms |
21924 KB |
Output is correct |
28 |
Correct |
4 ms |
21924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
21924 KB |
Output is correct |
2 |
Correct |
0 ms |
21924 KB |
Output is correct |
3 |
Correct |
0 ms |
21924 KB |
Output is correct |
4 |
Correct |
0 ms |
21924 KB |
Output is correct |
5 |
Correct |
0 ms |
21924 KB |
Output is correct |
6 |
Correct |
0 ms |
21924 KB |
Output is correct |
7 |
Correct |
0 ms |
21924 KB |
Output is correct |
8 |
Correct |
0 ms |
21924 KB |
Output is correct |
9 |
Correct |
0 ms |
21924 KB |
Output is correct |
10 |
Correct |
0 ms |
22116 KB |
Output is correct |
11 |
Correct |
0 ms |
21924 KB |
Output is correct |
12 |
Correct |
0 ms |
21924 KB |
Output is correct |
13 |
Correct |
0 ms |
21924 KB |
Output is correct |
14 |
Correct |
4 ms |
21924 KB |
Output is correct |
15 |
Correct |
8 ms |
21924 KB |
Output is correct |
16 |
Correct |
12 ms |
21924 KB |
Output is correct |
17 |
Correct |
12 ms |
21924 KB |
Output is correct |
18 |
Correct |
16 ms |
21924 KB |
Output is correct |
19 |
Correct |
0 ms |
22116 KB |
Output is correct |
20 |
Correct |
24 ms |
24232 KB |
Output is correct |
21 |
Correct |
4 ms |
21924 KB |
Output is correct |
22 |
Correct |
4 ms |
21924 KB |
Output is correct |
23 |
Correct |
0 ms |
21924 KB |
Output is correct |
24 |
Correct |
476 ms |
22308 KB |
Output is correct |
25 |
Correct |
720 ms |
23080 KB |
Output is correct |
26 |
Correct |
112 ms |
31144 KB |
Output is correct |
27 |
Correct |
476 ms |
58792 KB |
Output is correct |
28 |
Correct |
208 ms |
21924 KB |
Output is correct |
29 |
Correct |
316 ms |
21924 KB |
Output is correct |
30 |
Correct |
268 ms |
21924 KB |
Output is correct |
31 |
Correct |
16 ms |
21924 KB |
Output is correct |
32 |
Correct |
476 ms |
21924 KB |
Output is correct |
33 |
Correct |
0 ms |
21924 KB |
Output is correct |
34 |
Correct |
0 ms |
21924 KB |
Output is correct |
35 |
Correct |
252 ms |
22116 KB |
Output is correct |
36 |
Correct |
0 ms |
21924 KB |
Output is correct |
37 |
Correct |
4 ms |
21924 KB |
Output is correct |
38 |
Correct |
148 ms |
21924 KB |
Output is correct |
39 |
Correct |
160 ms |
21924 KB |
Output is correct |