oj.uz

Submission #236109

# Submission time Handle Problem Language Result Execution time Memory
236109 2020-05-31T08:32:36 Z NONAME Portal (COCI17_portal) C++17
96 / 120
 28 ms 5608 KB 
#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();

		if (dist > d[x][y])
			continue;

        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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1920 KB Output is correct
2 Correct 7 ms 2432 KB Output is correct
3 Correct 7 ms 1536 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4352 KB Output is correct
2 Correct 15 ms 2944 KB Output is correct
3 Correct 11 ms 3456 KB Output is correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4992 KB Output is correct
2 Correct 14 ms 5504 KB Output is correct
3 Correct 13 ms 3456 KB Output is correct
4 Incorrect 13 ms 4480 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 5608 KB Output isn't correct
2 Halted 0 ms 0 KB -