Submission #675329

#	Time	Username	Problem	Language	Result	Execution time	Memory
675329		vjudge1	Portals (BOI14_portals)	C++14	20 / 100	7 ms	7636 KiB

portals

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

using namespace std;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int n,m;
char a[1005][1005];
int f[1005][1005];
int t[1005][1005];
int b[1005][1005];
int l[1005][1005];
int r[1005][1005];
int edx , edy;

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

    memset(f,-1,sizeof f);

    queue <ii> q;

    cin >> n >> m;
    for(int i = 1; i <= n; i++) a[i][m+1] = a[i][0] ='#';
    for(int j = 1; j <= m; j++) a[n+1][j] = a[0][j] ='#';

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

        if(a[i][j] == 'C') edx = i, edy = j;

        if(a[i][j] == 'S')
        {
            q.push({i,j});
            f[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            l[i][j] = l[i][j-1];
            if(a[i][j] == '#') l[i][j] = j;
        }

        r[i][m+1] = m + 1;
        for (int j = m; j >= 1; j--)
        {
            r[i][j] = r[i][j+1];
            if(a[i][j] == '#') r[i][j] = j;
        }
    }

    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            t[i][j] = t[i-1][j];
            if(a[i][j] == '#') t[i][j] = i;
        }

        b[n+1][j] = n+1;
        for(int i = n; i >= 1; i--)
        {
            b[i][j] = b[i+1][j];
            if(a[i][j] == '#') b[i][j] = i;
        }
    }

    while(q.size())
    {
        int u = q.front().fi , v = q.front().se;
        q.pop();
        if(a[u][v] == '#') continue;
        if(u == edx && v == edy) return cout << f[u][v],0;
        for (int i = 0; i <= 3; i++)
        {
            int x = u + dx[i];
            int y = v + dy[i];
            if(x > 0 && x <= n && y > 0 && y <= m)
            if(f[x][y] == -1 && a[x][y] != '#')
            {
                f[x][y] = f[u][v] + 1;
                q.push({x,y});
            }
        }

        if(a[u-1][v] == '#' || a[u+1][v] == '#' || a[u][v-1] == '#' || a[u][v+1] == '#')
        {
            int x;

            x = t[u][v] + 1;
            if(f[x][v] == -1)
            {
                f[x][v] = f[u][v] + 1;
                q.push({x,v});
            }

            x = b[u][v] - 1;
            if(f[x][v] == -1)
            {
                f[x][v] = f[u][v] + 1;
                q.push({x,v});
            }

            x = l[u][v] + 1;
            if(f[u][x] == -1)
            {
                f[u][x] = f[u][v] + 1;
                q.push({u,x});
            }

            x = r[u][v] - 1;
            if(f[u][x] == -1)
            {
                f[u][x] = f[u][v] + 1;
                q.push({u,x});
            }
        }
    }


    return 0;
}

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