Submission #236077

#	Time	Username	Problem	Language	Result	Execution time	Memory
236077		VEGAnn	Portal (COCI17_portal)	C++14	120 / 120	97 ms	5888 KiB

portal

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define a3 array<int, 3>
using namespace std;
const int N = 510;
const int oo = 2e9;
set<a3> st;
int n, m, ex, ey, dst[N][N], step[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int net[4][N][N];
char c[N][N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        dst[i][j] = oo;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        cin >> c[i][j];

        if (c[i][j] == 'C'){
            dst[i][j] = 0;
            st.insert({dst[i][j], i, j});
            c[i][j] = '.';
        }

        if (c[i][j] == 'F'){
            ex = i;
            ey = j;
            c[i][j] = '.';
        }
    }

    for (int i = 0; i < n; i++){
        int lst = m;

        for (int j = m - 1; j >= 0; j--)
            if (c[i][j] == '#')
                lst = j;
            else net[0][i][j] = lst - 1;

        lst = -1;

        for (int j = 0; j < m; j++)
            if (c[i][j] == '#')
                lst = j;
            else net[1][i][j] = lst + 1;
    }

    for (int j = 0; j < m; j++){
        int lst = n;

        for (int i = n - 1; i >= 0; i--)
            if (c[i][j] == '#')
                lst = i;
            else net[2][i][j] = lst - 1;

        lst = -1;

        for (int i = 0; i < n; i++)
            if (c[i][j] == '#')
                lst = i;
            else net[3][i][j] = lst + 1;
    }

    while (sz(st) > 0){
        a3 CR = *st.begin(); st.erase(st.begin());

        int x = CR[1], y = CR[2];

        for (int it = 0; it < 4; it++){
            int cx = x + step[it][0], cy = y + step[it][1];

            if (cx < 0 || cy < 0 || cx >= n || cy >= m || c[cx][cy] == '#') continue;

            if (dst[cx][cy] > dst[x][y] + 1){
                st.erase({dst[cx][cy], cx, cy});
                dst[cx][cy] = dst[x][y] + 1;
                st.insert({dst[cx][cy], cx, cy});
            }
        }

        for (int wh = 0; wh < 4; wh++)
        for (int fr = 0; fr < 4; fr++){
            if (wh == fr) continue;

            int len = 0;

            if (fr < 2)
                len = abs(net[fr][x][y] - y) + 1;
            else len = abs(net[fr][x][y] - x) + 1;

            int cx = x, cy = y;

            if (wh < 2)
                cy = net[wh][x][y];
            else cx = net[wh][x][y];

            if (dst[cx][cy] > dst[x][y] + len){
                st.erase({dst[cx][cy], cx, cy});
                dst[cx][cy] = dst[x][y] + len;
                st.insert({dst[cx][cy], cx, cy});
            }
        }
    }

    if (dst[ex][ey] == oo)
        cout << "nemoguce";
    else cout << dst[ex][ey];

    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12