제출 #675284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675284		vjudge1	포탈들 (BOI14_portals)	C++14	0 / 100	3 ms	4436 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] = '#';
    for(int j = 1; j <= m; j++) a[n+1][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});
            }
        }

        int x;

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

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

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

        x = r[u][v] - 1;
        if(f[u][x] == -1 && a[u][v-1] == '#')
        {
            f[u][x] = f[u][v] + 1;
            q.push({u,x});
        }
    }
    return 0;
}

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