Submission #236151

#	Time	Username	Problem	Language	Result	Execution time	Memory
236151		NONAME	Portal (COCI17_portal)	C++17	120 / 120	39 ms	10752 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;

queue <pair <int, pair <int, int> > > q;
ll 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({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().ft, x = q.front().sd.ft, y = q.front().sd.sd;
		q.pop();

		dist = d[x][y];

        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 (c[cx][cy] != '#')
				if (dist + 1 < d[cx][cy]) {
					d[cx][cy] = dist + 1;
					q.push({d[cx][cy], {cx, cy}});
				}
        }

        int rast, cx, cy;

        /// UP
        {
        	rast = x - up[x][y] + 1;

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

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

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

        /// DOWN
        {
			rast = down[x][y] - x + 1;

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

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

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

        /// LEFT
        {
			rast = y - lft[x][y] + 1;

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

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

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

        /// RIGHT
        {
			rast = rgt[x][y] - y + 1;

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

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

            cx = x, cy = lft[x][y];
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {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: 12 / 12
• Subtask 10: 12 / 12