Submission #208709

#	Time	Username	Problem	Language	Result	Execution time	Memory
208709		E869120	Portals (BOI14_portals)	C++14	100 / 100	898 ms	85172 KiB

portals

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <tuple>
#include <functional>
using namespace std;

int H, W;
int sx, sy, gx, gy;
char c[1009][1009];
int dp[1009][1009];
vector<pair<int, int>> v[1009][1009];

int dist[1009][1009];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> Q;

int main() {
	// ステップ 1. 入力
	cin >> H >> W;
	for (int i = 0; i <= H + 1; i++) {
		for (int j = 0; j <= W + 1; j++) c[i][j] = '#';
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> c[i][j];
			if (c[i][j] == 'S') { sx = i; sy = j; c[i][j] = '.'; }
			if (c[i][j] == 'C') { gx = i; gy = j; c[i][j] = '.'; }
		}
	}
	H += 2; W += 2;

	// ステップ 2. グラフに辺を貼る
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) dp[i][j] = (1 << 30);
	}
	for (int i = 0; i < H; i++) {
		int last = 0;
		for (int j = 0; j < W; j++) {
			if (c[i][j] == '#') last = j;
			dp[i][j] = min(dp[i][j], abs(j - last));
			v[i][j].push_back(make_pair(i, last + 1));
		}
		last = 0;
		for (int j = W - 1; j >= 0; j--) {
			if (c[i][j] == '#') last = j;
			dp[i][j] = min(dp[i][j], abs(j - last));
			v[i][j].push_back(make_pair(i, last - 1));
		}
	}
	for (int j = 0; j < W; j++) {
		int last = 0;
		for (int i = 0; i < H; i++) {
			if (c[i][j] == '#') last = i;
			dp[i][j] = min(dp[i][j], abs(i - last));
			v[i][j].push_back(make_pair(last + 1, j));
		}
		last = 0;
		for (int i = H - 1; i >= 0; i--) {
			if (c[i][j] == '#') last = i;
			dp[i][j] = min(dp[i][j], abs(i - last));
			v[i][j].push_back(make_pair(last - 1, j));
		}
	}

	// ステップ 3. 最短距離計算
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) dist[i][j] = (1 << 30);
	}
	dist[sx][sy] = 0;
	Q.push(make_tuple(0, sx, sy));

	while (!Q.empty()) {
		int vx = get<1>(Q.top()), vy = get<2>(Q.top()); Q.pop();
		int dx[4] = { 0, 1, 0, -1 };
		int dy[4] = { 1, 0, -1, 0 };
		for (int i = 0; i < 4; i++) {
			int ex = vx + dx[i], ey = vy + dy[i];
			if (c[ex][ey] == '#') continue;
			if (dist[ex][ey] > dist[vx][vy] + 1) {
				dist[ex][ey] = dist[vx][vy] + 1;
				Q.push(make_tuple(dist[ex][ey], ex, ey));
			}
		}
		for (pair<int, int> i : v[vx][vy]) {
			int ex = i.first, ey = i.second;
			if (dist[ex][ey] > dist[vx][vy] + dp[vx][vy]) {
				dist[ex][ey] = dist[vx][vy] + dp[vx][vy];
				Q.push(make_tuple(dist[ex][ey], ex, ey));
			}
		}
	}

	cout << dist[gx][gy] << endl;
	return 0;
}

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