Submission #1215466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215466		stefanneagu	Maze (JOI23_ho_t3)	C++17	51 / 100	2102 ms	128584 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

deque<pair<int, int>> dq;
vector<vector<int>> mat, rasp;
vector<vector<bool>> f;
int n, m, k;
int si, ei, sj, ej;

bool in(int a, int b) {
    return (min({a, b, n - a + 1, m - b + 1}) > 0);
}

int val;

void ff(int a, int b) {
    if (!in(a, b) || mat[a][b] || f[a][b]) {
        return;
    }
    f[a][b] = 1;
    if (rasp[a][b] > val) {
        rasp[a][b] = val;
        dq.push_front({a, b});
    }
    ff(a + 1, b), ff(a, b + 1), ff(a - 1, b), ff(a, b - 1);
}

bool in_timbra(int i, int j) {
    int i1 = i - k, j1 = j - k;
    int i2 = i + k, j2 = j + k;
    if ((ei == i1 && ej == j1) || (ei == i2 && ej == j1) || (ei == i1 && ej == j2) || (ei == i2 && ej == j2)) {
        return 0;
    }
    if (i1 <= ei && ei <= i2 && j1 <= ej && ej <= j2) {
        return 1;
    }
    return 0;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> k >> si >> sj >> ei >> ej;
    rasp.resize(n + 1, vector<int>(m + 1, inf));
    mat.resize(n + 1, vector<int>(m + 1, 0));
    f.resize(n + 1, vector<bool>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char ch;
            cin >> ch;
            mat[i][j] = (ch == '.' ? 0 : 1);
        }
    }
    dq.push_front({si, sj});
    rasp[si][sj] = 0;
    int ans = inf;
    while (!dq.empty()) {
        auto [i, j] = dq.front();
        dq.pop_front();
        val = rasp[i][j];
        ff(i + 1, j);
        ff(i - 1, j);
        ff(i, j + 1);
        ff(i, j - 1);
        if (in_timbra(i, j)) {
            ans = min(ans, rasp[i][j] + 1);
        }
        // lat sus
        for (int j2 = max(1, j - k + 1); j2 <= min(m, j + k - 1); j2++) {
            if (rasp[max(1, i - k)][j2] > rasp[i][j] + 1) {
                rasp[max(1, i - k)][j2] = rasp[i][j] + 1;
                dq.push_back({max(1, i - k), j2});
            }
        }
        // lat dreapta
        for (int i2 = max(1, i - k + 1); i2 <= min(n, i + k - 1); i2++) {
            if (rasp[i2][min(m, j + k)] > rasp[i][j] + 1) {
                rasp[i2][min(m, j + k)] = rasp[i][j] + 1;
                dq.push_back({i2, min(m, j + k)});
            }
        }
        // lat jos
        for (int j2 = max(1, j - k + 1); j2 <= min(m, j + k - 1); j2++) {
            if (rasp[min(n, i + k)][j2] > rasp[i][j] + 1) {
                rasp[min(n, i + k)][j2] = rasp[i][j] + 1;
                dq.push_back({min(n, i + k), j2});
            }
        }
        // lat stanga
        for (int i2 = max(1, i - k + 1); i2 <= min(n, i + k - 1); i2++) {
            if (rasp[i2][max(1, j - k)] > rasp[i][j] + 1) {
                rasp[i2][max(1, j - k)] = rasp[i][j] + 1;
                dq.push_back({i2, max(1, j - k)});
            }
        }
    }
    cout << min(ans, rasp[ei][ej]);
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6