#include <bits/stdc++.h>
#define N 1003
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, m, xo, yo, xi, yi, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int id[N][N], cnt, dist[N*N];
char mat[N][N];
vector<pii> grafo[N*N];
inline int solve(int ini, int fim)
{
priority_queue<pii, vector<pii>, greater<pii> > fila;
memset(dist, 0x3f3f3f3f, sizeof dist);
dist[ini] = 0;
fila.push({0, ini});
while(!fila.empty())
{
int x = fila.top().s, d = fila.top().f;
fila.pop();
if(x == fim) break;
if(d > dist[x]) continue;
for(auto v: grafo[x])
{
if(dist[v.f] > dist[x] + v.s)
{
dist[v.f] = dist[x] + v.s;
fila.push({dist[v.f], v.f});
}
}
}
return dist[fim];
}
pii esq[N][N], dir[N][N], baixo[N][N], cima[N][N];
inline void fill()
{
for(int i = 1; i <= n; i++)
{
int ultimo = 0;
for(int j = 1; j <= m; j++)
{
if(mat[i][j] == '#') ultimo = j;
esq[i][j] = {i, ultimo + 1};
}
ultimo = m + 1;
for(int j = m; j >= 1; j--)
{
if(mat[i][j] == '#') ultimo = j;
dir[i][j] = {i, ultimo - 1};
}
}
for(int j = 1; j <= m; j++)
{
int ultimo = 0;
for(int i = 1; i <= n; i++)
{
if(mat[i][j] == '#') ultimo = i;
cima[i][j] = {ultimo + 1, j};
}
ultimo = n + 1;
for(int i = n; i >= 1; i --)
{
if(mat[i][j] == '#') ultimo = i;
baixo[i][j] = {ultimo - 1, j};
}
}
}
inline int get(){
int n = 0, x;
for(x=getchar();x<'0'||x>'9';x=getchar()){}
for(;x>='0'&& x<='9';x=getchar()) n = (n<<3) + (n<<1) + x - '0';
return n;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
n = get(), m = get();
for(int i = 0; i <= n + 1; i++)
for(int j = 0; j <= m + 1; j++)
id[i][j] = ++ cnt;
for(int i = 0; i <= n + 1; i++)
{
for(int j = 0; j <= m + 1; j++)
{
if(!i or i == n + 1 or !j or j == m + 1)
{
mat[i][j] = '#';
continue;
}
mat[i][j] = getchar();
if(mat[i][j] == 'S') xo = i, yo = j;
if(mat[i][j] == 'C') xi = i, yi = j;
if(j == m) getchar();
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
int x = id[i][j];
if(mat[i][j] != '#')
{
for(int p = 0; p < 4; p++)
{
int a = i + dx[p], b = j + dy[p];
if(a < 0 or b < 0 or a > n + 1 or b > m + 1) continue;
if(mat[a][b] != '#') grafo[x].push_back({id[a][b], 1});
}
}
}
}
fill();
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(mat[i][j] == '#') continue;
vector< pii > pos;
pos.push_back(esq[i][j]), pos.push_back(dir[i][j]);
pos.push_back(baixo[i][j]), pos.push_back(cima[i][j]);
int x = id[i][j], custo = 2000000000;
for(int a = 0; a < pos.size(); a++)
{
int A = abs(i - pos[a].f) + abs(j - pos[a].s);
custo = min(custo, A + 1);
}
for(int a = 0; a < pos.size(); a++) grafo[x].push_back({id[pos[a].f][pos[a].s], custo});
}
}
cout<<solve(id[xo][yo], id[xi][yi])<<"\n";
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:176:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = 0; a < pos.size(); a++)
~~^~~~~~~~~~~~
portals.cpp:183:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = 0; a < pos.size(); a++) grafo[x].push_back({id[pos[a].f][pos[a].s], custo});
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
27900 KB |
Output is correct |
2 |
Correct |
37 ms |
28132 KB |
Output is correct |
3 |
Correct |
24 ms |
28168 KB |
Output is correct |
4 |
Correct |
24 ms |
28244 KB |
Output is correct |
5 |
Correct |
25 ms |
28320 KB |
Output is correct |
6 |
Correct |
25 ms |
28368 KB |
Output is correct |
7 |
Correct |
24 ms |
28396 KB |
Output is correct |
8 |
Correct |
25 ms |
28400 KB |
Output is correct |
9 |
Correct |
24 ms |
28400 KB |
Output is correct |
10 |
Correct |
26 ms |
28420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
28420 KB |
Output is correct |
2 |
Correct |
27 ms |
28524 KB |
Output is correct |
3 |
Correct |
29 ms |
28524 KB |
Output is correct |
4 |
Correct |
27 ms |
28524 KB |
Output is correct |
5 |
Correct |
30 ms |
28524 KB |
Output is correct |
6 |
Correct |
25 ms |
28524 KB |
Output is correct |
7 |
Correct |
26 ms |
28524 KB |
Output is correct |
8 |
Correct |
25 ms |
28524 KB |
Output is correct |
9 |
Correct |
29 ms |
29548 KB |
Output is correct |
10 |
Correct |
27 ms |
29548 KB |
Output is correct |
11 |
Correct |
26 ms |
29548 KB |
Output is correct |
12 |
Correct |
26 ms |
29548 KB |
Output is correct |
13 |
Correct |
26 ms |
29548 KB |
Output is correct |
14 |
Correct |
27 ms |
29548 KB |
Output is correct |
15 |
Correct |
27 ms |
29548 KB |
Output is correct |
16 |
Correct |
25 ms |
29548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
29548 KB |
Output is correct |
2 |
Correct |
29 ms |
29548 KB |
Output is correct |
3 |
Correct |
26 ms |
29548 KB |
Output is correct |
4 |
Correct |
29 ms |
29548 KB |
Output is correct |
5 |
Correct |
68 ms |
35392 KB |
Output is correct |
6 |
Correct |
48 ms |
35580 KB |
Output is correct |
7 |
Correct |
46 ms |
35708 KB |
Output is correct |
8 |
Correct |
47 ms |
35856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
35856 KB |
Output is correct |
2 |
Correct |
29 ms |
35856 KB |
Output is correct |
3 |
Correct |
27 ms |
35856 KB |
Output is correct |
4 |
Correct |
25 ms |
35856 KB |
Output is correct |
5 |
Correct |
25 ms |
35856 KB |
Output is correct |
6 |
Correct |
33 ms |
35856 KB |
Output is correct |
7 |
Correct |
34 ms |
35856 KB |
Output is correct |
8 |
Correct |
32 ms |
35856 KB |
Output is correct |
9 |
Correct |
32 ms |
35856 KB |
Output is correct |
10 |
Correct |
31 ms |
35856 KB |
Output is correct |
11 |
Correct |
31 ms |
35856 KB |
Output is correct |
12 |
Correct |
27 ms |
35856 KB |
Output is correct |
13 |
Correct |
29 ms |
35856 KB |
Output is correct |
14 |
Correct |
52 ms |
35856 KB |
Output is correct |
15 |
Correct |
46 ms |
35856 KB |
Output is correct |
16 |
Correct |
47 ms |
35856 KB |
Output is correct |
17 |
Correct |
47 ms |
35856 KB |
Output is correct |
18 |
Correct |
55 ms |
36068 KB |
Output is correct |
19 |
Correct |
46 ms |
36732 KB |
Output is correct |
20 |
Correct |
62 ms |
36732 KB |
Output is correct |
21 |
Correct |
45 ms |
36732 KB |
Output is correct |
22 |
Correct |
55 ms |
36732 KB |
Output is correct |
23 |
Correct |
45 ms |
36732 KB |
Output is correct |
24 |
Correct |
53 ms |
36732 KB |
Output is correct |
25 |
Correct |
25 ms |
36732 KB |
Output is correct |
26 |
Correct |
30 ms |
36732 KB |
Output is correct |
27 |
Correct |
32 ms |
36732 KB |
Output is correct |
28 |
Correct |
55 ms |
36732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
36732 KB |
Output is correct |
2 |
Correct |
25 ms |
36732 KB |
Output is correct |
3 |
Correct |
25 ms |
36732 KB |
Output is correct |
4 |
Correct |
26 ms |
36732 KB |
Output is correct |
5 |
Correct |
26 ms |
36732 KB |
Output is correct |
6 |
Correct |
28 ms |
36732 KB |
Output is correct |
7 |
Correct |
28 ms |
36732 KB |
Output is correct |
8 |
Correct |
29 ms |
36732 KB |
Output is correct |
9 |
Correct |
34 ms |
36732 KB |
Output is correct |
10 |
Correct |
29 ms |
36732 KB |
Output is correct |
11 |
Correct |
27 ms |
36732 KB |
Output is correct |
12 |
Correct |
27 ms |
36732 KB |
Output is correct |
13 |
Correct |
27 ms |
36732 KB |
Output is correct |
14 |
Correct |
53 ms |
36732 KB |
Output is correct |
15 |
Correct |
67 ms |
36732 KB |
Output is correct |
16 |
Correct |
48 ms |
36732 KB |
Output is correct |
17 |
Correct |
48 ms |
36732 KB |
Output is correct |
18 |
Correct |
50 ms |
36732 KB |
Output is correct |
19 |
Correct |
60 ms |
36988 KB |
Output is correct |
20 |
Correct |
75 ms |
36988 KB |
Output is correct |
21 |
Correct |
46 ms |
36988 KB |
Output is correct |
22 |
Correct |
50 ms |
36988 KB |
Output is correct |
23 |
Correct |
54 ms |
36988 KB |
Output is correct |
24 |
Correct |
663 ms |
118524 KB |
Output is correct |
25 |
Execution timed out |
1090 ms |
142992 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |