Submission #492482

#	Time	Username	Problem	Language	Result	Execution time	Memory
492482		Rainbowbunny	Portals (BOI14_portals)	C++17	100 / 100	221 ms	181688 KiB

portals

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
const int INF = 1e9;

int r, c;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int sx, sy, ex, ey;
pair <int, int> d[4][MAXN][MAXN];
int dist[MAXN][MAXN], H[MAXN][MAXN];
char a[MAXN][MAXN];
vector <pair <int, int> > Dist[MAXN * MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> r >> c;
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 'S')
            {
                sx = i, sy = j;
            }
            else if(a[i][j] == 'C')
            {
                ex = i, ey = j;
            }
        }
    }
    for(int i = 1; i <= r; i++)
    {
        d[0][i][0] = make_pair(i, 1);
        for(int j = 1; j <= c; j++)
        {
            if(a[i][j] == '#')
            {
                d[0][i][j] = make_pair(i, j + 1);
            }
            else
            {
                d[0][i][j] = d[0][i][j - 1];
            }
        }
        d[1][i][c + 1] = make_pair(i, c);
        for(int j = c; j >= 1; j--)
        {
            if(a[i][j] == '#')
            {
                d[1][i][j] = make_pair(i, j - 1);
            }
            else
            {
                d[1][i][j] = d[1][i][j + 1];
            }
        }
    }
    for(int j = 1; j <= c; j++)
    {
        d[2][0][j] = make_pair(1, j);
        for(int i = 1; i <= r; i++)
        {
            if(a[i][j] == '#')
            {
                d[2][i][j] = make_pair(i + 1, j);
            }
            else
            {
                d[2][i][j] = d[2][i - 1][j];
            }
        }
        d[3][r + 1][j] = make_pair(r, j);
        for(int i = r; i >= 1; i--)
        {
            if(a[i][j] == '#')
            {
                d[3][i][j] = make_pair(i - 1, j);
            }
            else
            {
                d[3][i][j] = d[3][i + 1][j];
            }
        }
    }
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            dist[i][j] = INF;
            H[i][j] = INF;
        }
    }
    dist[sx][sy] = 0;
    queue <pair <int, int> > BFS;
    for(int i = 0; i <= r + 1; i++)
    {
        for(int j = 0; j <= c + 1; j++)
        {
            if(a[i][j] == '#' or i == 0 or i == r + 1 or j == 0 or j == c + 1)
            {
                BFS.emplace(i, j);
                H[i][j] = 0;
            }
        }
    }
    while(BFS.empty() == false)
    {
        int nx = BFS.front().first, ny = BFS.front().second;
        BFS.pop();
        for(int i = 0; i < 4; i++)
        {
            int tx = nx + dx[i], ty = ny + dy[i];
            if(H[tx][ty] > H[nx][ny] + 1)
            {
                H[tx][ty] = H[nx][ny] + 1;
                BFS.emplace(tx, ty);
            }
        }
    }
    Dist[0].emplace_back(sx, sy);
    for(int i = 0; i < MAXN * MAXN; i++)
    {
        while(!Dist[i].empty())
        {
            int nx = Dist[i].back().first, ny = Dist[i].back().second;
            Dist[i].pop_back();
            if(dist[nx][ny] != i)
            {
                continue;
            }
            for(int j = 0; j < 4; j++)
            {
                int tx = nx + dx[j], ty = ny + dy[j];
                if(dist[tx][ty] > dist[nx][ny] + 1 and tx > 0 and ty > 0 and tx <= r and ty <= c and a[tx][ty] != '#')
                {
                    dist[tx][ty] = dist[nx][ny] + 1;
                    Dist[i + 1].emplace_back(tx, ty);
                }
                tx = d[j][nx][ny].first, ty = d[j][nx][ny].second;
                if(dist[tx][ty] > dist[nx][ny] + H[nx][ny])
                {
                    dist[tx][ty] = dist[nx][ny] + H[nx][ny];
                    Dist[dist[nx][ny] + H[nx][ny]].emplace_back(tx, ty);
                }
            }
        }
    }
    cout << dist[ex][ey] << '\n';
}

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