Submission #943270

#	Time	Username	Problem	Language	Result	Execution time	Memory
943270		itslq	Portals (BOI14_portals)	C++17	20 / 100	4 ms	17496 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)};
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;
    if (x < 0 || y < 0 || x >= R || y >= C || grid[x][y] || visited[x][y]) return;
    visited[x][y] = 1;
    tocheck.emplace(make_pair(x, y), n + 1);
        //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;
    cin >> R >> C;

    //int left[R][C], right[R][C], up[R][C], down[R][C];
    string row;

    //visited = vector<vector<bool>>(R, vector<bool>(C, 0));

    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<pair<int, int>, int> curr;
    add(si, sj, -1);
    //return 0;

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

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

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

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

        for (pair<int, int> d: dirs) add(ci + d.first, cj + d.second, curr.second);
        if (cj == 0 || cj == C - 1 || ci == 0 || ci == R - 1 || grid[ci][cj + 1] || grid[ci][cj - 1] || grid[ci + 1][cj] || grid[ci - 1][cj]) {
            add(ci, LA[ci][cj], curr.second);
            add(ci, RA[ci][cj], curr.second);
            add(UA[ci][cj], cj, curr.second);
            add(DA[ci][cj], cj, curr.second);
        }
    }
}

Compilation message (stderr)

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

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