Submission #129750

#	Time	Username	Problem	Language	Result	Execution time	Memory
129750		SamAnd	Portals (BOI14_portals)	C++17	100 / 100	379 ms	47432 KiB

portals

#include <bits/stdc++.h>
using namespace std;
const int N = 1003;
const int xx[4] = {1, 0, -1, 0};
const int yy[4] = {0, 1, 0, -1};
struct ban
{
    int x, y, d;
    ban(){}
    ban(int x, int y, int d)
    {
        this->x = x;
        this->y = y;
        this->d = d;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

int n, m;
char a[N][N];
int sx, sy;
int cx, cy;

int l[N][N], r[N][N], u[N][N], d[N][N];
int minu[N][N];

bool c[N][N];
int djk()
{
    priority_queue<ban> q;
    q.push(ban(sx, sy, 0));
    while (1)
    {
        ban t;
        do
        {
            t = q.top();
            q.pop();
        } while (c[t.x][t.y]);
        c[t.x][t.y] = true;
        if (t.x == cx && t.y == cy)
            return t.d;
        for (int i = 0; i < 4; ++i)
        {
            ban h = t;
            h.x += xx[i];
            h.y += yy[i];
            h.d++;
            if (h.x >= 1 && h.x <= n && h.y >= 1 && h.y <= m && a[h.x][h.y] == '.' && !c[h.x][h.y])
            {
                q.push(h);
            }
        }
        if (!c[t.x][r[t.x][t.y] - 1])
            q.push(ban(t.x, r[t.x][t.y] - 1, t.d + minu[t.x][t.y]));
        if (!c[t.x][l[t.x][t.y] + 1])
            q.push(ban(t.x, l[t.x][t.y] + 1, t.d + minu[t.x][t.y]));
        if (!c[u[t.x][t.y] + 1][t.y])
            q.push(ban(u[t.x][t.y] + 1, t.y, t.d + minu[t.x][t.y]));
        if (!c[d[t.x][t.y] - 1][t.y])
            q.push(ban(d[t.x][t.y] - 1, t.y, t.d + minu[t.x][t.y]));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> a[i][j];
            if (a[i][j] == 'S')
            {
                a[i][j] = '.';
                sx = i;
                sy = j;
            }
            if (a[i][j] == 'C')
            {
                a[i][j] = '.';
                cx = i;
                cy = j;
            }
        }
    }
    for (int i = 0; i <= n + 1; ++i)
    {
        a[i][0] = '#';
        a[i][m + 1] = '#';
    }
    for (int j = 0; j <= m + 1; ++j)
    {
        a[0][j] = '#';
        a[n + 1][j] = '#';
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            if (a[i][j] == '#')
                l[i][j] = j;
            else
                l[i][j] = l[i][j - 1];
        }
        for (int j = m + 1; j >= 1; --j)
        {
            if (a[i][j] == '#')
                r[i][j] = j;
            else
                r[i][j] = r[i][j + 1];
        }
    }
    for (int j = 1; j <= m; ++j)
    {
        for (int i = 0; i <= n; ++i)
        {
            if (a[i][j] == '#')
                u[i][j] = i;
            else
                u[i][j] = u[i - 1][j];
        }
        for (int i = n + 1; i >= 1; --i)
        {
            if (a[i][j] == '#')
                d[i][j] = i;
            else
                d[i][j] = d[i + 1][j];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == '.')
                minu[i][j] = min(min(j - l[i][j], r[i][j] - j), min(i - u[i][j], d[i][j] - i));
        }
    }
    cout << djk() << endl;
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30