Submission #1068403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068403		vjudge1	Portals (BOI14_portals)	C++11	0 / 100	1 ms	348 KiB

portals

#include <iostream>
#include <climits>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;

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

    ll r, c;
    cin >> r >> c;
    string m[r];
    ll dist[r][c], minX[r], minY[c];
    pair<ll, ll> s, k;
    vector<pair<ll, ll>> adj[r][c];
    for (ll i=0; i<r; i++) {
        minX[i] = 0;
        cin >> m[i];
        for (ll j=0; j<c; j++) {
            if (i == 0) {
                minY[j] = 0;
            }
            dist[i][j] = -1;
            if (m[i][j] == '#') {
                adj[i][j-1].push_back({i, minX[i]});
                adj[i][minX[i]].push_back({i, j-1});
                adj[i-1][j].push_back({minY[j], j});
                adj[minY[j]][j].push_back({i-1, j});
                minX[i] = j+1;
                minY[j] = i+1;
            } else {
                if (minY[j] != i) {
                    adj[i-1][j].push_back({i, j});
                    adj[i][j].push_back({i-1, j});
                }
                if (minX[i] != j) {
                    adj[i][j-1].push_back({i, j});
                    adj[i][j].push_back({i, j-1});
                }
                if (m[i][j] == 'S') {
                    s = {i, j};
                } else if (m[i][j] == 'C') {
                    k = {i, j};
                }
            }
        }
    }

    queue<pair<ll, ll>> bfs;
    bfs.push(s);
    while (!bfs.empty()) {
        pair<ll, ll> f = bfs.front();
        bfs.pop();
        if (s == f) {
            dist[f.first][f.second] = 0;
        }
        for (pair<ll, ll> x : adj[f.first][f.second]) {
            if (dist[x.first][x.second] == -1) {
                dist[x.first][x.second] = dist[f.first][f.second]+1;
                if (x == k) {
                    cout << dist[x.first][x.second];
                    return 0;
                }
                bfs.push(x);
            }
        }
    }
}

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