oj.uz

Submission #117347

# Submission time Handle Problem Language Result Execution time Memory
117347 2019-06-15T14:20:03 Z FutymyClone Portal (COCI17_portal) C++14
120 / 120
 38 ms 7808 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] == 'C') 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] == 'F') ans = d[i][j];
    if (ans > 1e9) cout << "nemoguce";
    else cout << ans;
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2432 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2316 KB Output is correct

Subtask #3
12.0 / 12.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

Subtask #4
12.0 / 12.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

Subtask #5
12.0 / 12.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 Correct 4 ms 2432 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3584 KB Output is correct
2 Correct 5 ms 3200 KB Output is correct
3 Correct 7 ms 3328 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3968 KB Output is correct
2 Correct 7 ms 4352 KB Output is correct
3 Correct 7 ms 3584 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6192 KB Output is correct
2 Correct 18 ms 5120 KB Output is correct
3 Correct 14 ms 5240 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7264 KB Output is correct
2 Correct 21 ms 7652 KB Output is correct
3 Correct 23 ms 5568 KB Output is correct
4 Correct 19 ms 6272 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7688 KB Output is correct
2 Correct 24 ms 7808 KB Output is correct
3 Correct 31 ms 7720 KB Output is correct
4 Correct 35 ms 7692 KB Output is correct