Submission #674450

#	Time	Username	Problem	Language	Result	Execution time	Memory
674450		flashhh	Portals (BOI14_portals)	C++17	100 / 100	293 ms	26384 KiB

portals

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define eb emplace

using namespace std;

struct spInfo{
    int distance, row, column;

    spInfo() {}
    spInfo(int _distance, int _row, int _column) {
        distance = _distance; row = _row; column = _column;
    }
};
        
bool operator <(const spInfo &x, const spInfo &y) {
    return (x.distance > y.distance);
}

int xCoordinate[4] = {-1,0,0,1};
int yCoordinate[4] = {0,-1,1,0};

int numRow,numColumn;
pair<int,int> cakeCoordinate,mainCoordinate;
vector<vector<char> > labyrinth;
vector<vector<int> > distances;

void fastIO() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

void Read() {
    cin >> numRow >> numColumn;

    labyrinth.resize(numRow);
    for (int row = 0; row < numRow; ++row) labyrinth[row].resize(numColumn);

    for (int row = 0; row < numRow; ++row)
        for (int column = 0; column < numColumn; ++column) {
            cin >> labyrinth[row][column];

            if (labyrinth[row][column] == 'S') mainCoordinate = {row, column};
            if (labyrinth[row][column] == 'C') cakeCoordinate = {row, column};
        }    
}

void calculate() {
    vector<vector<int> > nearestSide;

    auto buildNearestSide = [&] () -> void {
        nearestSide.resize(numRow);
        for (int row = 0; row < numRow; ++row) nearestSide[row].resize(numColumn);

        for (int row = 0; row < numRow; ++row)
            for (int column = 0; column < numColumn; ++column) {
                if (labyrinth[row][column] == '#') {
                    nearestSide[row][column] = -1;
                    continue;
                }

                nearestSide[row][column] = (int)1e9;

                for (int direction = 0; direction < 4; ++direction) {
                    int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
                    if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn || labyrinth[adjRow][adjColumn] == '#') {
                        nearestSide[row][column] = 0;
                        break;
                    }
                }
            }
        
        queue<pair<int,int> > myQueue;
        for (int row = 0; row < numRow; ++row)
            for (int column = 0; column < numColumn; ++column)
                if (nearestSide[row][column] == 0) myQueue.emplace(row, column);
        
        while (!myQueue.empty()) {
            auto [row, column] = myQueue.front(); myQueue.pop();
            
            for (int direction = 0; direction < 4; ++direction) {
                int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
                if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn) continue;

                if (nearestSide[adjRow][adjColumn] > nearestSide[row][column] + 1) {
                    nearestSide[adjRow][adjColumn] = nearestSide[row][column] + 1;
                    myQueue.emplace(adjRow, adjColumn);
                }
            }
        }
    };

    vector<vector<int> > leftMostWall, rightMostWall, topMostWall, bottomMostWall;

    auto buildNearestWall = [&] () -> void {
        leftMostWall.resize(numRow); rightMostWall.resize(numRow);
        for (int row = 0; row < numRow; ++row) {
            leftMostWall[row].resize(numColumn);
            rightMostWall[row].resize(numColumn);
        }

        for (int row = 0; row < numRow; ++row) {
            int lastColumn = -1;
            for (int column = 0; column < numColumn; ++column) 
                if (labyrinth[row][column] == '#') lastColumn = column;
            else leftMostWall[row][column] = column - lastColumn;
            
            lastColumn = numColumn;
            for (int column = numColumn - 1; column >= 0; --column)
                if (labyrinth[row][column] == '#') lastColumn = column;
            else rightMostWall[row][column] = lastColumn - column;
        }

        topMostWall.resize(numRow); bottomMostWall.resize(numRow);
        for (int row = 0; row < numRow; ++row) {
            topMostWall[row].resize(numColumn);
            bottomMostWall[row].resize(numColumn);
        }

        for (int column = 0; column < numColumn; ++column) {
            int lastRow = -1;
            for (int row = 0; row < numRow; ++row)
                if (labyrinth[row][column] == '#') lastRow = row;
            else topMostWall[row][column] = row - lastRow;

            lastRow = numRow;
            for (int row = numRow - 1; row >= 0; --row)
                if (labyrinth[row][column] == '#') lastRow = row;
            else bottomMostWall[row][column] = lastRow - row;
        }
    };

    buildNearestSide();
    buildNearestWall();

    auto buildDistance = [&] () -> void {
        priority_queue<spInfo> prioQueue;

        distances.resize(numRow);
        for (int row = 0; row < numRow; ++row) distances[row].resize(numColumn, (int)1e9);

        distances[mainCoordinate.first][mainCoordinate.second] = 0;
        prioQueue.emplace(0, mainCoordinate.first, mainCoordinate.second);

        auto updatePrioQueue = [&] (int row, int column, int val) -> void{
            if (distances[row][column] > val) {
                distances[row][column] = val;
                prioQueue.emplace(distances[row][column], row, column);
            }
        };

        while (!prioQueue.empty()) {
            auto [distance, row, column] = prioQueue.top(); prioQueue.pop();
            if (distances[row][column] != distance) continue;

            for (int direction = 0; direction < 4; ++direction) {
                int adjRow = row + xCoordinate[direction]; int adjColumn = column + yCoordinate[direction];
                if (adjRow < 0 || adjRow >= numRow || adjColumn < 0 || adjColumn >= numColumn || labyrinth[adjRow][adjColumn] == '#') continue;

                updatePrioQueue(adjRow, adjColumn, distance + 1);
            }

            int xTeleport, yTeleport;

            xTeleport = row; yTeleport = column - leftMostWall[row][column] + 1;
            updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);

            xTeleport = row; yTeleport = column + rightMostWall[row][column] - 1;
            updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);

            xTeleport = row - topMostWall[row][column] + 1; yTeleport = column;
            updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);

            xTeleport = row + bottomMostWall[row][column] - 1; yTeleport = column;
            updatePrioQueue(xTeleport, yTeleport, distance + nearestSide[row][column] + 1);
        }
    };

    buildDistance();
}

void printAnswer() {
    cout << distances[cakeCoordinate.first][cakeCoordinate.second] <<'\n';
}

int main() {
    fastIO();
    Read();

    calculate();
    printAnswer();

    return 0;
}

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