#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
bool open[1002][1002];
int n, m, visited[1002][1002], to_wall[1002][1002];
vector<pair<int, pair<int, int>>> graph[1002][1002];
pair<int, int> src, dest;
inline bool has_wall(int x, int y) {
return !(open[x - 1][y] && open[x + 1][y] && open[x][y - 1] && open[x][y + 1]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
char c;
cin >> c;
if (c != '#') open[i][j] = true;
if (c == 'S') src = {i, j};
if (c == 'C') dest = {i, j};
}
FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
if (open[i - 1][j]) graph[i][j].push_back({1, {i - 1, j}});
if (open[i + 1][j]) graph[i][j].push_back({1, {i + 1, j}});
if (open[i][j - 1]) graph[i][j].push_back({1, {i, j - 1}});
if (open[i][j + 1]) graph[i][j].push_back({1, {i, j + 1}});
}
queue<pair<int, int>> q;
FOR(i, 0, n + 2) FOR(j, 0, m + 2) {
if (open[i][j] && has_wall(i, j)) {
to_wall[i][j] = 1;
q.push({i, j});
}
}
while (q.size()) {
pair<int, int> curr = q.front();
q.pop();
for (pair<int, pair<int, int>> i : graph[curr.first][curr.second]) {
if (!to_wall[i.second.first][i.second.second]) {
to_wall[i.second.first][i.second.second] = to_wall[curr.first][curr.second] + 1;
q.push(i.second);
}
}
}
pair<int, int> bound;
bool has;
FOR(i, 0, n + 1) FOR(j, 0, m + 1) {
if (!open[i][j]) has = false;
else {
if (!has) bound = {i, j};
else graph[i][j].push_back({to_wall[i][j], bound});
has = true;
}
}
FOR(j, 0, m + 1) FOR(i, 0, n + 1) {
if (!open[i][j]) has = false;
else {
if (!has) bound = {i, j};
else graph[i][j].push_back({to_wall[i][j], bound});
has = true;
}
}
for (int i = n + 1; i; i--) for (int j = m + 1; j; j--) {
if (!open[i][j]) has = false;
else {
if (!has) bound = {i, j};
else graph[i][j].push_back({to_wall[i][j], bound});
has = true;
}
}
for (int j = m + 1; j; j--) for (int i = n + 1; i; i--) {
if (!open[i][j]) has = false;
else {
if (!has) bound = {i, j};
else graph[i][j].push_back({to_wall[i][j], bound});
has = true;
}
}
priority_queue<pair<int, pair<int, int>>> pq;
pq.push({-1, src});
while (pq.size()) {
int dist = pq.top().first;
pair<int, int> curr = pq.top().second;
pq.pop();
if (!visited[curr.first][curr.second]) {
visited[curr.first][curr.second] = -dist;
for (pair<int, pair<int, int>> i : graph[curr.first][curr.second]) {
pq.push({dist - i.first, i.second});
}
}
if (curr == dest) break;
}
cout << visited[dest.first][dest.second] - 1;
return 0;
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:84:13: warning: 'has' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (!has) bound = {i, j};
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
23928 KB |
Output is correct |
2 |
Correct |
19 ms |
23928 KB |
Output is correct |
3 |
Correct |
20 ms |
24056 KB |
Output is correct |
4 |
Correct |
20 ms |
24056 KB |
Output is correct |
5 |
Correct |
20 ms |
24056 KB |
Output is correct |
6 |
Correct |
21 ms |
24056 KB |
Output is correct |
7 |
Correct |
19 ms |
24056 KB |
Output is correct |
8 |
Correct |
20 ms |
24056 KB |
Output is correct |
9 |
Correct |
20 ms |
24056 KB |
Output is correct |
10 |
Correct |
20 ms |
23928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23928 KB |
Output is correct |
2 |
Correct |
19 ms |
23928 KB |
Output is correct |
3 |
Correct |
19 ms |
24056 KB |
Output is correct |
4 |
Correct |
19 ms |
23928 KB |
Output is correct |
5 |
Correct |
20 ms |
24056 KB |
Output is correct |
6 |
Correct |
20 ms |
24056 KB |
Output is correct |
7 |
Correct |
20 ms |
23960 KB |
Output is correct |
8 |
Correct |
22 ms |
24184 KB |
Output is correct |
9 |
Correct |
23 ms |
24824 KB |
Output is correct |
10 |
Correct |
23 ms |
24824 KB |
Output is correct |
11 |
Correct |
21 ms |
24568 KB |
Output is correct |
12 |
Correct |
22 ms |
24568 KB |
Output is correct |
13 |
Correct |
24 ms |
24568 KB |
Output is correct |
14 |
Correct |
20 ms |
24056 KB |
Output is correct |
15 |
Correct |
22 ms |
24696 KB |
Output is correct |
16 |
Correct |
21 ms |
23928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23928 KB |
Output is correct |
2 |
Correct |
20 ms |
24056 KB |
Output is correct |
3 |
Correct |
20 ms |
24056 KB |
Output is correct |
4 |
Correct |
20 ms |
24056 KB |
Output is correct |
5 |
Correct |
45 ms |
28280 KB |
Output is correct |
6 |
Correct |
52 ms |
28540 KB |
Output is correct |
7 |
Correct |
50 ms |
29176 KB |
Output is correct |
8 |
Correct |
39 ms |
28536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
23928 KB |
Output is correct |
2 |
Correct |
20 ms |
24056 KB |
Output is correct |
3 |
Correct |
20 ms |
24056 KB |
Output is correct |
4 |
Correct |
20 ms |
23928 KB |
Output is correct |
5 |
Correct |
19 ms |
24056 KB |
Output is correct |
6 |
Correct |
20 ms |
23996 KB |
Output is correct |
7 |
Correct |
20 ms |
24056 KB |
Output is correct |
8 |
Correct |
20 ms |
24056 KB |
Output is correct |
9 |
Correct |
24 ms |
24828 KB |
Output is correct |
10 |
Correct |
21 ms |
24824 KB |
Output is correct |
11 |
Correct |
22 ms |
24568 KB |
Output is correct |
12 |
Correct |
22 ms |
24568 KB |
Output is correct |
13 |
Correct |
23 ms |
24568 KB |
Output is correct |
14 |
Correct |
46 ms |
28408 KB |
Output is correct |
15 |
Correct |
53 ms |
28536 KB |
Output is correct |
16 |
Correct |
49 ms |
29176 KB |
Output is correct |
17 |
Correct |
57 ms |
29176 KB |
Output is correct |
18 |
Correct |
68 ms |
30072 KB |
Output is correct |
19 |
Correct |
43 ms |
29816 KB |
Output is correct |
20 |
Correct |
59 ms |
31740 KB |
Output is correct |
21 |
Correct |
47 ms |
28412 KB |
Output is correct |
22 |
Correct |
48 ms |
28408 KB |
Output is correct |
23 |
Correct |
50 ms |
28664 KB |
Output is correct |
24 |
Correct |
114 ms |
31064 KB |
Output is correct |
25 |
Correct |
20 ms |
23928 KB |
Output is correct |
26 |
Correct |
21 ms |
24568 KB |
Output is correct |
27 |
Correct |
20 ms |
23928 KB |
Output is correct |
28 |
Correct |
37 ms |
28536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23928 KB |
Output is correct |
2 |
Correct |
20 ms |
23928 KB |
Output is correct |
3 |
Correct |
21 ms |
24056 KB |
Output is correct |
4 |
Correct |
24 ms |
24056 KB |
Output is correct |
5 |
Correct |
20 ms |
24056 KB |
Output is correct |
6 |
Correct |
20 ms |
24056 KB |
Output is correct |
7 |
Correct |
21 ms |
24056 KB |
Output is correct |
8 |
Correct |
20 ms |
24056 KB |
Output is correct |
9 |
Correct |
25 ms |
24824 KB |
Output is correct |
10 |
Correct |
23 ms |
24824 KB |
Output is correct |
11 |
Correct |
22 ms |
24568 KB |
Output is correct |
12 |
Correct |
23 ms |
24568 KB |
Output is correct |
13 |
Correct |
22 ms |
24696 KB |
Output is correct |
14 |
Correct |
46 ms |
28280 KB |
Output is correct |
15 |
Correct |
65 ms |
28632 KB |
Output is correct |
16 |
Correct |
48 ms |
29176 KB |
Output is correct |
17 |
Correct |
57 ms |
29052 KB |
Output is correct |
18 |
Correct |
73 ms |
29944 KB |
Output is correct |
19 |
Correct |
45 ms |
29816 KB |
Output is correct |
20 |
Correct |
62 ms |
31740 KB |
Output is correct |
21 |
Correct |
48 ms |
28408 KB |
Output is correct |
22 |
Correct |
47 ms |
28408 KB |
Output is correct |
23 |
Correct |
50 ms |
28664 KB |
Output is correct |
24 |
Execution timed out |
1099 ms |
124868 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |