#include <bits/stdc++.h>
using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int sx, sy, cx, cy;
vector<vector<int>> wall(n, vector<int>(m, 1e7));
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == 'S') {
sx = i;
sy = j;
}
if (s[i][j] == 'C') {
cx = i;
cy = j;
}
if (s[i][j] == '#') {
v.emplace_back(i, j);
wall[i][j] = -1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == '#') continue;
if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
v.emplace_back(i, j);
wall[i][j] = 0;
}
}
}
for (int i = 0; i < v.size(); i++) {
int x = v[i].first, y = v[i].second;
for (int d = 0; d < 4; d++) {
int ni = x + dx[d], nj = y + dy[d];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && wall[ni][nj] > wall[x][y] + 1) {
wall[ni][nj] = wall[x][y] + 1;
v.emplace_back(ni, nj);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
assert(wall[i][j] != 1e7);
}
}
vector<vector<pair<int, int>>> up(n, vector<pair<int, int>>(m));
vector<vector<pair<int, int>>> down(n, vector<pair<int, int>>(m));
vector<vector<pair<int, int>>> left(n, vector<pair<int, int>>(m));
vector<vector<pair<int, int>>> right(n, vector<pair<int, int>>(m));
//up
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] != '#') {
if (i == 0 || up[i - 1][j] == make_pair(-1, -1)) {
up[i][j] = make_pair(i, j);
} else {
up[i][j] = up[i - 1][j];
}
} else {
up[i][j] = make_pair(-1, -1);
}
}
}
//down
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (s[i][j] != '#') {
if (i == n - 1 || down[i + 1][j] == make_pair(-1, -1)) {
down[i][j] = make_pair(i, j);
} else {
down[i][j] = down[i + 1][j];
}
} else {
down[i][j] = make_pair(-1, -1);
}
}
}
//left
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (s[i][j] != '#') {
if (j == 0 || left[i][j - 1] == make_pair(-1, -1)) {
left[i][j] = make_pair(i, j);
} else {
left[i][j] = left[i][j - 1];
}
} else {
left[i][j] = make_pair(-1, -1);
}
}
}
//right
for (int j = m - 1; j >= 0; j--) {
for (int i = 0; i < n; i++) {
if (s[i][j] != '#') {
if (j == m - 1 || right[i][j + 1] == make_pair(-1, -1)) {
right[i][j] = make_pair(i, j);
} else {
right[i][j] = right[i][j + 1];
}
} else {
right[i][j] = make_pair(-1, -1);
}
}
}
vector<vector<vector<tuple<int, int, int>>>> g(n, vector<vector<tuple<int, int, int>>>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == '#') continue;
bool ok = false;
if (up[i][j] == make_pair(i, j)) {
ok = true;
}
if (down[i][j] == make_pair(i, j)) {
ok = true;
}
if (left[i][j] == make_pair(i, j)) {
ok = true;
}
if (right[i][j] == make_pair(i, j)) {
ok = true;
}
if (ok || false) {
for (auto nn : {up[i][j], down[i][j], left[i][j], right[i][j]}) {
if (nn == make_pair(-1, -1)) {
continue;
}
g[i][j].emplace_back(nn.first, nn.second, wall[i][j] + 1);
}
}
for (int foo = 0; foo < 4; foo++) {
int ni = i + dx[foo], nj = j + dy[foo];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && s[ni][nj] != '#') {
g[i][j].emplace_back(ni, nj, 1);
}
}
}
}
set<tuple<int, int, int>> q;
q.insert({0, sx, sy});
vector<vector<int>> dist(n, vector<int>(m, 1e9));
dist[sx][sy] = 0;
while (!q.empty()) {
auto it = *q.begin();
int x = get<1>(it);
int y = get<2>(it);
int dd = get<0>(it);
q.erase(q.begin());
if (dd > dist[x][y]) {
continue;
}
for (auto c : g[x][y]) {
int w = get<2>(c);
if (dist[get<0>(c)][get<1>(c)] > dist[x][y] + w) {
dist[get<0>(c)][get<1>(c)] = dist[x][y] + w;
q.insert({dist[get<0>(c)][get<1>(c)], get<0>(c), get<1>(c)});
}
}
}
int ans = dist[cx][cy];
cout << (ans == 1e9 ? -1 : ans) << '\n';
return 0;
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
portals.cpp:174:24: warning: 'cy' may be used uninitialized in this function [-Wmaybe-uninitialized]
174 | int ans = dist[cx][cy];
| ^
portals.cpp:156:14: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
156 | dist[sx][sy] = 0;
| ^
portals.cpp:156:10: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
156 | dist[sx][sy] = 0;
| ^
portals.cpp:174:20: warning: 'cx' may be used uninitialized in this function [-Wmaybe-uninitialized]
174 | int ans = dist[cx][cy];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
10 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
14 ms |
5700 KB |
Output is correct |
6 |
Correct |
16 ms |
5908 KB |
Output is correct |
7 |
Correct |
17 ms |
6064 KB |
Output is correct |
8 |
Correct |
12 ms |
6092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |