oj.uz

Submission #122478

# Submission time Handle Problem Language Result Execution time Memory
122478 2019-06-28T11:24:54 Z FutymyClone Portals (BOI14_portals) C++14
0 / 100
 6 ms 2560 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int n, m, d[N][N], nxt[N][N][4], f[N][N];
char a[N][N];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

bool in (int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

bool in2 (int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != '#';
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '#') nxt[i][j][0] = j;
            else nxt[i][j][0] = nxt[i][j - 1][0];
        }

        for (int j = m; j >= 1; j--) {
            if (a[i][j] == '#') nxt[i][j][2] = j;
            else nxt[i][j][2] = nxt[i][j + 1][2];
        }
    }

    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][j] == '#') nxt[i][j][1] = i;
            else nxt[i][j][1] = nxt[i - 1][j][1];
        }

        for (int i = n; i >= 1; i--) {
            if (a[i][j] == '#') nxt[i][j][3] = i;
            else nxt[i][j][3] = nxt[i + 1][j][3];
        }
    }

    memset(f, 0x3f, sizeof(f));
    queue <pair <int, int> > q;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] == '#') f[i][j] = 0, q.push({i, j});
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second; q.pop();
        for (int i = 0; i < 4; i++) {
            if (in(x + dx[i], y + dy[i]) && f[x + dx[i]][y + dy[i]] > f[x][y] + 1) {
                f[x + dx[i]][y + dy[i]] = f[x][y] + 1;
                q.push({x + dx[i], y + dy[i]});
            }
        }
    }

    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] == 'S') d[i][j] = 0, q.push({i, j});
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second; q.pop();
        for (int i = 0; i < 4; i++) {
            if (in2(x + dx[i], y + dy[i]) && d[x + dx[i]][y + dy[i]] > d[x][y] + 1) {
                d[x + dx[i]][y + dy[i]] = d[x][y] + 1;
                q.push({x + dx[i], y + dy[i]});
            }
        }

        for (int i = 0; i <= 2; i += 2) {
            int ny = nxt[x][y][i];
            if (y < ny) {
                if (in2(x, ny - 1) && d[x][ny - 1] > d[x][y] + f[x][y]) {
                    d[x][ny - 1] = d[x][y] + f[x][y];
                    q.push({x, ny - 1});
                }
            }
            else {
                if (in2(x, ny + 1) && d[x][ny + 1] > d[x][y] + f[x][y]) {
                    d[x][ny + 1] = d[x][y] + f[x][y];
                    q.push({x, ny + 1});
                }
            }
        }

        for (int i = 1; i <= 3; i += 2) {
            int nx = nxt[x][y][i];
            if (x < nx) {
                if (in2(nx - 1, y) && d[nx - 1][y] > d[x][y] + f[x][y]) {
                    d[nx - 1][y] = d[x][y] + f[x][y];
                    q.push({nx - 1, y});
                }
            }
            else {
                if (in2(nx + 1, y) && d[nx + 1][y] > d[x][y] + f[x][y]) {
                    d[nx + 1][y] = d[x][y] + f[x][y];
                    q.push({nx + 1, y});
                }
            }
        }
    }

    int ans = -1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] == 'C') ans = d[i][j];
    cout << ans;
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2432 KB Output is correct
2 Correct 4 ms 2560 KB Output is correct
3 Incorrect 4 ms 2432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2432 KB Output is correct
2 Correct 3 ms 2432 KB Output is correct
3 Incorrect 4 ms 2432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Incorrect 4 ms 2432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Incorrect 4 ms 2432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2304 KB Output is correct
2 Correct 5 ms 2432 KB Output is correct
3 Incorrect 4 ms 2432 KB Output isn't correct
4 Halted 0 ms 0 KB -