Submission #675332

#	Time	Username	Problem	Language	Result	Execution time	Memory
675332		vjudge1	Portals (BOI14_portals)	C++14	0 / 100	3 ms	4380 KiB

portals

#include <bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second

using namespace std;

int R, C, i, j;
char a[1005][1005];
int wL[1005][1005][2], wR[1005][1005][2];
int t[1005][1005];
int cx, cy;
queue< pair<int, int> > q;

void bfs(int x, int y)
{
    if (x >= 0 && y >= 0 && x < C && y < R && t[y][x] == -1 && a[y][x] != '#')
    {
        t[y][x] = t[j][i] + 1;
        q.push(make_pair(x, y));
    }
}

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

    memset(t,-1,sizeof t);

    cin >> R >> C;

    for (int j = 0; j < R; j++)
    {
        for (int i = 0; i < C; i++) cin >> a[j][i];

        for (int i = 0; i < C; i++)
        {
            t[j][i] = -1;
            if(a[j][i] == 'S')
            {
                t[j][i] = 0;
                q.push({i,j});
            }
            if(a[j][i] == 'C')
            {
                cx = i;
                cy = j;
            }
        }
    }

    for (int j = 0; j < R; j++)
        for (int i = 0; i < C; i++)
        {
            wR[j][i][0] = wR[j-1][i][0];
            if(a[j-1][i] == '#') wR[j][i][0] = j;

            wL[j][i][0] = wL[j][i-1][0];
            if(a[j][i-1] == '#') wL[j][i][0] = i;
        }

    for (int j = R-1; j >= 0; j--)
    for (int i = C-1; i >= 0; i--)
    {
        wR[j][i][1] = wR[j+1][i][1];
        if(a[j+1][i] == '#') wR[j][i][1] = j;

        wL[j][i][1] = wL[j][i+1][1];
        if(a[j][i] == '#') wL[i][j][1] = i;
    }

    while (q.size() && t[cy][cx] == -1)
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        bfs(i, j-1);
        bfs(i, j+1);
        bfs(i-1, j);
        bfs(i+1, j);
        if (wL[j][i][0] == i || wL[j][i][1] == i || wR[j][i][0] == j || wR[j][i][1] == j)
        {
            bfs(wL[j][i][0], j);
            bfs(wL[j][i][1], j);
            bfs(i, wR[j][i][0]);
            bfs(i, wR[j][i][1]);
        }
    }

    cout << t[cy][cx];
}

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