Submission #943201

#	Time	Username	Problem	Language	Result	Execution time	Memory
943201		itslq	Portals (BOI14_portals)	C++17	0 / 100	1 ms	604 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;
vector<vector<int>> visited;
bool grid[1000][1000];

void add(int x, int y, int n) {
    if (x < 0 || y < 0 || x >= R || x >= C) return;
    if (grid[x][y] || visited[x][y]) return;

    visited[x][y] = 1;
    tocheck.emplace(make_pair(x, y), n + 1);
}

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<int>>(R, vector<int>(C, 0));

    for (int i = 0; i < R; i++) {
        P = 0;
        cin >> row;
        for (int j = 0; j < C; j++) {
            left[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--) {
            right[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++) {
            up[i][j] = P;
            if (grid[i][j]) P = i + 1;
        }

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

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

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

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

        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);
        add(ci, left[ci][cj], curr.second);
        add(ci, right[ci][cj], curr.second);
        add(up[ci][cj], cj, curr.second);
        add(down[ci][cj], cj, curr.second);
    }
}

Compilation message (stderr)

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

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