Submission #726446

#	Time	Username	Problem	Language	Result	Execution time	Memory
726446		Tigerpants	Portals (BOI14_portals)	C++17	70 / 100	1086 ms	99600 KiB

portals

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#include <queue>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;


#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define sz(a) a.size()
#define pb(a) push_back(a)

const ll INF = 1000000000;

vvll wall;
vvll goal;
vvll dp;
vvll portal[4]; // for each of the 4 directions, get the distance to the wall...

pll start;
pll cake;
ll R, C;
vvb board;

ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};

void calc_wall();
void calc_goal();
void calc_portal();

bool dp_compare(pll a, pll b) {
    if (dp[a.first][a.second] == dp[b.first][b.second]) {
        if (a.first == b.first) return a.second < b.second;
        return a.first < b.first;
    }
    return dp[a.first][a.second] < dp[b.first][b.second];
}
set<pll, decltype(dp_compare)*> BFS(dp_compare);

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

    cin >> R >> C;
    board.resize(R + 2);
    char tmp;
    board[0].resize(C + 2);
    board[R + 1].resize(C + 2);
    rep(j, 0, C + 2) {board[0][j] = false; board[R + 1][j] = false;}
    rep(i, 1, R + 1) {
        board[i].resize(C + 2);
        board[i][0] = false;
        board[i][C + 1] = false;
        rep(j, 1, C + 1) {
            cin >> tmp;
            board[i][j] = (tmp != '#');
            if (tmp == 'S') {
                start = mp(i, j);
            }
            if (tmp == 'C') {
                cake = mp(i, j);
            }
        }
    }
    R += 2;
    C += 2;

    wall.resize(R);
    goal.resize(R);
    dp.resize(R);
    rep(i, 0, 4) portal[i].resize(R);

    rep(i, 0, R) {
        wall[i].resize(C);
        goal[i].resize(C);
        dp[i].resize(C);
        rep(j, 0, 4) portal[j][i].resize(C);
        rep(j, 0, C) dp[i][j] = INF;
    }

    // calculate supporting values
    calc_wall();
    calc_goal();
    calc_portal();

    // do BFS in dp graph...
    dp[start.first][start.second] = 0;

    rep(i, 0, R) {
        rep(j, 0, C) {
            if (board[i][j]) BFS.insert(mp(i, j));
        }
    }

    while (!BFS.empty()) {
        pll pos = *BFS.begin();
        BFS.erase(BFS.begin());
        
        rep(k, 0, 4) {
            // try walking
            pll next = mp(pos.first + dx[k], pos.second + dy[k]);
            if (BFS.find(next) != BFS.end()) {
                BFS.erase(next);
                dp[next.first][next.second] = min<ll>(dp[next.first][next.second], dp[pos.first][pos.second] + 1);
                BFS.insert(next);
            }

            // try shooting
            next = mp(pos.first + (dx[k] * portal[k][pos.first][pos.second]), pos.second + (dy[k] * portal[k][pos.first][pos.second]));
            if (BFS.find(next) != BFS.end()) {
                BFS.erase(next);
                dp[next.first][next.second] = min<ll>(dp[next.first][next.second], dp[pos.first][pos.second] + wall[pos.first][pos.second]);
                BFS.insert(next);
            }

        }
    }

    cout << dp[cake.first][cake.second] << endl;

    return 0;
}

void calc_wall() {
    vvb vis(R, vb(C, false));
    vpll p, q;
    rep(i, 0, R) {
        rep(j, 0, C) {
            if (!board[i][j]) {
                q.pb(mp(i, j));
                wall[i][j] = 0;
                vis[i][j] = true;
            }
        }
    }
    while (!q.empty()) {
        for (vpll::iterator itr = q.begin(); itr != q.end(); itr++) {
            rep(d, 0, 4) {
                pll next = mp(itr->first + dx[d], itr->second + dy[d]);
                if ((next.first == -1) || (next.second == -1) || (next.first == R) || (next.second == C)) continue;
                if (!vis[next.first][next.second]) {
                    vis[next.first][next.second] = true;
                    wall[next.first][next.second] = wall[itr->first][itr->second] + 1;
                    p.pb(next);
                }
            }
        }
        swap(p, q);
        p.clear();
    }
}

void calc_goal() {
    vvb vis(R, vb(C, false));
    goal[cake.first][cake.second] = 0;
    vpll q;
    vpll p;
    q.pb(cake);
    while (!q.empty()) {
        for (vpll::iterator itr = q.begin(); itr != q.end(); itr++) {
            rep(d, 0, 4) {
                pll next = mp(itr->first + dx[d], itr->second + dy[d]);
                if ((!vis[next.first][next.second]) && (board[next.first][next.second])) {
                    vis[next.first][next.second] = true;
                    goal[next.first][next.second] = goal[itr->first][itr->second] + 1;
                    p.pb(next);
                }
            }
        }
        swap(p, q);
        p.clear();
    }
}

ll portal_dp(ll i, ll j, ll k) {
    if (portal[k][i][j] == -2) portal[k][i][j] = portal_dp(i + dx[k], j + dy[k], k) + 1;
    return portal[k][i][j];
}

void calc_portal() {
    // setup before call dp
    rep(i, 0, R) {
        rep(j, 0, C) {
            rep(k, 0, 4) {
                portal[k][i][j] = -1 -(board[i][j]);
            }
        }
    }

    rep(i, 0, R) {
        rep(j, 0, C) {
            rep(k, 0, 4) {
                portal_dp(i, j, k);
            }
        }
    }
}

// There is a (RC)^3 dp
// There is also a (RC)^2 dp: if there are 2 portals then one should b-line to one of them

// For each cell we define the following distances:
// Distance to cell before nearest wall
// Distance to goal
// Then from each cell we can do one of 3 operations:
// Move a step up/down/left/right
// Shoot a portal to a wall up/down/left/right and go to nearest wall to appear at where we shot
// Move to goal
// This gives us a 9*RC dp with RC statest and 9 edges per state...

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