Submission #943310

#	Time	Username	Problem	Language	Result	Execution time	Memory
943310		itslq	Portals (BOI14_portals)	C++17	100 / 100	335 ms	44100 KiB

portals

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

int R, C;
const pair<int, int> dirs[4] = {make_pair(0, 1), make_pair(0, -1), make_pair(1, 0), make_pair(-1, 0)};
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> tocheck;
//queue<pair<pair<int, int>, int>> tocheck;
bool visited[1000][1000], grid[1000][1000];
int LA[1000][1000], RA[1000][1000], UA[1000][1000], DA[1000][1000];

void add(int x, int y, int n) {
    //cout << R << " " << C << endl;
//    cout << x << " " << y << " " << n << endl;
//    cout << grid[x][y] << " " << visited[x][y] << endl;
    if (x < 0 || y < 0 || x >= R || y >= C || grid[x][y] || visited[x][y]) return;
    tocheck.emplace(n + 1, make_pair(x, y));
     //cout << x << " " << y << " " << n << endl;
       //cout << x << " " << y << " " << n + 1 << endl;
}

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

    int P = 0, si, sj, ei, ej, ni, nj, ci, cj, dist;
    cin >> R >> C;

    string row;

    for (int i = 0; i < R; i++) {
        memset(visited[i], 0, sizeof(visited[i]));

        P = 0;
        cin >> row;
        for (int j = 0; j < C; j++) {
            LA[i][j] = P;
            switch (row[j]) {
                case '.':
                    grid[i][j] = 0;
                    break;
                case '#':
                    grid[i][j] = 1;
                    P = j + 1;
                    break;
                case 'S':
                    si = i;
                    sj = j;
                    grid[i][j] = 0;
                    break;
                case 'C':
                    ei = i;
                    ej = j;
                    grid[i][j] = 0;
                    break;
            }
        }

        P = C - 1;
        for (int j = C - 1; j >= 0; j--) {
            RA[i][j] = P;
            if (grid[i][j]) P = j - 1;
        }
    }

    for (int j = 0; j < C; j++) {
        P = 0;
        for (int i = 0; i < R; i++) {
            UA[i][j] = P;
            if (grid[i][j]) P = i + 1;
        }

        P = R - 1;
        for (int i = R - 1; i >= 0; i--) {
            DA[i][j] = P;
            if (grid[i][j]) P = i - 1;
        }
    }

    pair<int, pair<int, int>> curr;
    add(si, sj, -1);
    //return 0;

    while (true) {
        curr = tocheck.top();
        tocheck.pop();

        ci = curr.second.first;
        cj = curr.second.second;

        //cout << ci << " " << cj << " " << curr.first << endl;

        if (visited[ci][cj]) continue;
        visited[ci][cj] = 1;

        //cout << ci << " " << cj << " " << curr.second << endl;

        if (ci == ei && cj == ej) {
            cout << curr.first;
            return 0;
        }

        for (pair<int, int> d: dirs) add(ci + d.first, cj + d.second, curr.first);

        if (cj == 0 || cj == C - 1 || ci == 0 || ci == R - 1) dist = 0;
        else dist = min(min(abs(LA[ci][cj] - cj), abs(RA[ci][cj] - cj)), min(abs(UA[ci][cj] - ci), abs(DA[ci][cj] - ci)));

        add(ci, LA[ci][cj], curr.first + dist);
        add(ci, RA[ci][cj], curr.first + dist);
        add(UA[ci][cj], cj, curr.first + dist);
        add(DA[ci][cj], cj, curr.first + dist);
    }
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:25:32: warning: unused variable 'ni' [-Wunused-variable]
   25 |     int P = 0, si, sj, ei, ej, ni, nj, ci, cj, dist;
      |                                ^~
portals.cpp:25:36: warning: unused variable 'nj' [-Wunused-variable]
   25 |     int P = 0, si, sj, ei, ej, ni, nj, ci, cj, dist;
      |                                    ^~
portals.cpp:97:28: warning: 'ej' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |         if (ci == ei && cj == ej) {
      |                         ~~~^~~~~
portals.cpp:97:16: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |         if (ci == ei && cj == ej) {
      |             ~~~^~~~~
portals.cpp:80:8: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |     add(si, sj, -1);
      |     ~~~^~~~~~~~~~~~
portals.cpp:80:8: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]

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