# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42227 | 2018-02-23T19:16:48 Z | gabrielsimoes | Portals (BOI14_portals) | C++14 | 2 ms | 772 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 210, INF = 1e9; typedef pair<int, int> pii; int n, m; bool open[MAXN][MAXN]; pii start, cake; // int ix(pii p) { return (p.first - 1) * m + p.second - 1; } // pii pr(int ix) { return pii(ix / m + 1, (ix % n) + 1); } // left, right, north, south int limit[MAXN][MAXN][4]; bool ok[MAXN][MAXN]; int dist[MAXN][MAXN]; int bfs() { for (int i = 1; i <= n; i++) for (int k = 1; k <= m; k++) dist[i][k] = INF; queue<pii> q; q.push(start); dist[start.first][start.second] = 0; while (!q.empty()) { int x, y; tie(x, y) = q.front(); q.pop(); for (int i = 0; i < 8; i++) { int nx = x, ny = y; if (i == 0) nx--; if (i == 1) nx++; if (i == 2) ny--; if (i == 3) ny++; if (i == 4) nx += limit[x][y][0]; if (i == 5) nx += limit[x][y][1]; if (i == 6) ny += limit[x][y][2]; if (i == 7) ny += limit[x][y][3]; if (open[nx][ny] && !ok[nx][ny]) { dist[nx][ny] = dist[x][y] + 1; ok[nx][ny] = 1; q.push(pii(nx, ny)); } } } return dist[cake.first][cake.second]; } int main() { scanf("%d %d", &n, &m); char c; for (int i = 1; i <= n; i++) { for (int k = 1; k <= m; k++) { scanf(" %c", &c); if (c != '#') open[i][k] = 1; if (c == 'S') start = pii(i, k); if (c == 'C') cake = pii(i, k); } } for (int i = 1; i <= n; i++) { int last_wall = 0; for (int k = 1; k <= m; k++) { if (open[i][k]) limit[i][k][0] = k - last_wall - 1; else last_wall = k; } last_wall = m + 1; for (int k = m; k >= 1; k--) { if (open[i][k]) limit[i][k][1] = last_wall - k - 1; else last_wall = k; } } for (int k = 1; k <= m; k++) { int last_wall = 0; for (int i = 1; i <= n; i++) { if (open[i][k]) limit[i][k][2] = i - last_wall - 1; else last_wall = i; } last_wall = n + 1; for (int i = n; i >= 1; i--) { if (open[i][k]) limit[i][k][3] = last_wall - i - 1; else last_wall = i; } } printf("%d\n", bfs()); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 248 KB | Output is correct |
2 | Correct | 1 ms | 484 KB | Output is correct |
3 | Incorrect | 2 ms | 592 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 700 KB | Output is correct |
2 | Correct | 2 ms | 700 KB | Output is correct |
3 | Incorrect | 2 ms | 700 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 700 KB | Output is correct |
2 | Correct | 1 ms | 724 KB | Output is correct |
3 | Incorrect | 1 ms | 728 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 748 KB | Output is correct |
2 | Correct | 1 ms | 752 KB | Output is correct |
3 | Incorrect | 1 ms | 756 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 764 KB | Output is correct |
2 | Correct | 1 ms | 768 KB | Output is correct |
3 | Incorrect | 2 ms | 772 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |