# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
656449 | 2022-11-07T14:13:02 Z | 600Mihnea | Portals (BOI14_portals) | C++17 | 4 ms | 1876 KB |
bool home = 0; #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1000 + 7; int n; int m; int a[N][N]; int r1; int c1; int r2; int c2; /// a[i][j] == 1 => (i, j) is a free cell int dr[] = {-1, 0, 1, 0}; int dc[] = {0, 1, 0, -1}; int d[N][N]; signed main() { if (home == 0) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } else { freopen ("___input___.txt", "r", stdin); } cin >> n >> m; for (int i = 1; i <= n; i++) { string s; cin >> s; assert((int) s.size() == m); for (int j = 1; j <= m; j++) { char ch = s[j - 1]; assert(ch == '.' || ch == '#' || ch == 'S' || ch == 'C'); if (ch != '#') { a[i][j] = 1; } if (ch == 'S') { assert(r1 == 0 && c1 == 0); r1 = i; c1 = j; } if (ch == 'C') { assert(r2 == 0 && c2 == 0); r2 = i; c2 = j; } d[i][j] = -1; } } assert(1 <= r1 && r1 <= n); assert(1 <= r2 && r2 <= n); assert(1 <= c1 && c1 <= m); assert(1 <= c2 && c2 <= m); queue<pair<int, int>> q; q.push({r1, c1}); d[r1][c1] = 0; while (!q.empty()) { int r = q.front().first; int c = q.front().second; q.pop(); bool some_wall = 0; for (int k = 0; k < 4; k++) { int rn = r + dr[k]; int cn = c + dc[k]; if (a[rn][cn] == 0) { some_wall = 1; } if (a[rn][cn] == 1 && d[rn][cn] == -1) { d[rn][cn] = 1 + d[r][c]; q.push({rn, cn}); } } if (some_wall) { for (int k = 0; k < 4; k++) { int rn = r; int cn = c; while (a[rn + dr[k]][cn + dc[k]] == 1) { rn += dr[k]; cn += dc[k]; } if (d[rn][cn] == -1) { d[rn][cn] = 1 + d[r][c]; q.push({rn, cn}); } } } } assert(d[r2][c2] != -1); cout << d[r2][c2] << "\n"; return 0; } /// :15
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Incorrect | 0 ms | 340 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 328 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 724 KB | Output is correct |
10 | Incorrect | 1 ms | 724 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 3 ms | 1876 KB | Output is correct |
6 | Correct | 4 ms | 1848 KB | Output is correct |
7 | Correct | 4 ms | 1876 KB | Output is correct |
8 | Correct | 2 ms | 1876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 328 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 724 KB | Output is correct |
10 | Incorrect | 1 ms | 724 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 336 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 724 KB | Output is correct |
10 | Incorrect | 1 ms | 724 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |