Submission #236111

#	Time	Username	Problem	Language	Result	Execution time	Memory
236111		NONAME	Portal (COCI17_portal)	C++17	96 / 120	27 ms	5504 KiB

portal

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define ft first
#define sd second
#define pb push_back
#define ppb pop_back
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
using namespace std;

typedef long long ll;
typedef long double ld;

struct st {
	int dist, x, y;

	st (int dist, int x, int y) : dist(dist), x(x), y(y) {}
};

queue <st> q;
int lft[505][505], rgt[505][505], down[505][505], up[505][505], d[505][505], n, m, ex, ey;
char c[505][505];

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
		d[i][j] = 1e9;

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

		if (c[i][j] == 'C')
            q.push(st(0, i, j)), d[i][j] = 0;

		if (c[i][j] == 'F')
			ex = i, ey = 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 - 1;
				else rgt[i][j] = lst;

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

	for (int j = 0; j < m; j++) {
        int lst = n;
        for (int i = n - 1; i >= 0; i--)
			if (c[i][j] == '#') lst = i - 1;
				else down[i][j] = lst;

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

    while (!q.empty()) {
		int dist = q.front().dist, x = q.front().x, y = q.front().y;
		q.pop();

        int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (int i = 0; i < 4; i++) {
            int cx = x + steps[i][0];
            int cy = y + steps[i][1];

            if (cx >= 0 && cx < n && cy >= 0 && cy < m && c[cx][cy] != '#')
				if (dist + 1 < d[cx][cy]) {
					d[cx][cy] = dist + 1;
					q.push(st(dist + 1, cx, cy));
				}
        }

        if (x + 1 < n && c[x + 1][y] == '#') {
            int cx, cy;
            cx = up[x][y], cy = y;
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }

            cx = x, cy = lft[x][y];
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }

            cx = x, cy = rgt[x][y];
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }
        }

        if (x - 1 >= 0 && c[x - 1][y] == '#') {
            int cx, cy;
            cx = down[x][y], cy = y;
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }

            cx = x, cy = lft[x][y];
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }

            cx = x, cy = rgt[x][y];
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }
        }

        if (y + 1 < m && c[x][y + 1] == '#') {
            int cx, cy;
            cx = up[x][y], cy = y;
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }

            cx = down[x][y], cy = y;
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }

            cx = x, cy = lft[x][y];
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }
        }

        if (y - 1 >= 0 && c[x][y - 1] == '#') {
            int cx, cy;
            cx = up[x][y], cy = y;
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }

            cx = down[x][y], cy = y;
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }

            cx = x, cy = rgt[x][y];
            if (dist + 1 < d[cx][cy]) {
				d[cx][cy] = dist + 1;
				q.push(st(dist + 1, cx, cy));
            }
        }
    }

	if (d[ex][ey] == 1e9) cout << "nemoguce";
		else cout << d[ex][ey];
}

• 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: 0 / 12
• Subtask 10: 0 / 12