| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 943270 |
2024-03-11T09:47:43 Z |
itslq |
Portals (BOI14_portals) |
C++17 |
|
4 ms |
17496 KB |
#include <bits/stdc++.h>
using namespace std;
int R, C;
const pair<int, int> dirs[4] = {make_pair(0, 1), make_pair(0, -1), make_pair(1, 0), make_pair(-1, 0)};
queue<pair<pair<int, int>, int>> tocheck;
bool visited[1000][1000], grid[1000][1000];
int LA[1000][1000], RA[1000][1000], UA[1000][1000], DA[1000][1000];
void add(int x, int y, int n) {
//cout << R << " " << C << endl;
//cout << x << " " << y << " " << n << endl;
if (x < 0 || y < 0 || x >= R || y >= C || grid[x][y] || visited[x][y]) return;
visited[x][y] = 1;
tocheck.emplace(make_pair(x, y), n + 1);
//cout << x << " " << y << " " << n + 1 << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int P = 0, si, sj, ei, ej, ni, nj, ci, cj;
cin >> R >> C;
//int left[R][C], right[R][C], up[R][C], down[R][C];
string row;
//visited = vector<vector<bool>>(R, vector<bool>(C, 0));
for (int i = 0; i < R; i++) {
memset(visited[i], 0, sizeof(visited[i]));
P = 0;
cin >> row;
for (int j = 0; j < C; j++) {
LA[i][j] = P;
switch (row[j]) {
case '.':
grid[i][j] = 0;
break;
case '#':
grid[i][j] = 1;
P = j + 1;
break;
case 'S':
si = i;
sj = j;
grid[i][j] = 0;
break;
case 'C':
ei = i;
ej = j;
grid[i][j] = 0;
break;
}
}
P = C - 1;
for (int j = C - 1; j >= 0; j--) {
RA[i][j] = P;
if (grid[i][j]) P = j - 1;
}
}
for (int j = 0; j < C; j++) {
P = 0;
for (int i = 0; i < R; i++) {
UA[i][j] = P;
if (grid[i][j]) P = i + 1;
}
P = R - 1;
for (int i = R - 1; i >= 0; i--) {
DA[i][j] = P;
if (grid[i][j]) P = i - 1;
}
}
pair<pair<int, int>, int> curr;
add(si, sj, -1);
//return 0;
while (true) {
curr = tocheck.front();
tocheck.pop();
ci = curr.first.first;
cj = curr.first.second;
//cout << ci << " " << cj << " " << curr.second << endl;
if (ci == ei && cj == ej) {
cout << curr.second;
return 0;
}
for (pair<int, int> d: dirs) add(ci + d.first, cj + d.second, curr.second);
if (cj == 0 || cj == C - 1 || ci == 0 || ci == R - 1 || grid[ci][cj + 1] || grid[ci][cj - 1] || grid[ci + 1][cj] || grid[ci - 1][cj]) {
add(ci, LA[ci][cj], curr.second);
add(ci, RA[ci][cj], curr.second);
add(UA[ci][cj], cj, curr.second);
add(DA[ci][cj], cj, curr.second);
}
}
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:23:32: warning: unused variable 'ni' [-Wunused-variable]
23 | int P = 0, si, sj, ei, ej, ni, nj, ci, cj;
| ^~
portals.cpp:23:36: warning: unused variable 'nj' [-Wunused-variable]
23 | int P = 0, si, sj, ei, ej, ni, nj, ci, cj;
| ^~
portals.cpp:93:28: warning: 'ej' may be used uninitialized in this function [-Wmaybe-uninitialized]
93 | if (ci == ei && cj == ej) {
| ~~~^~~~~
portals.cpp:93:16: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
93 | if (ci == ei && cj == ej) {
| ~~~^~~~~
portals.cpp:81:8: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | add(si, sj, -1);
| ~~~^~~~~~~~~~~~
portals.cpp:81:8: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8668 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 8 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8664 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
4 ms |
17252 KB |
Output is correct |
| 6 |
Correct |
4 ms |
17496 KB |
Output is correct |
| 7 |
Correct |
4 ms |
17244 KB |
Output is correct |
| 8 |
Correct |
3 ms |
17244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8664 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
