Submission #497758

#	Time	Username	Problem	Language	Result	Execution time	Memory
497758		MilosMilutinovic	Portals (BOI14_portals)	C++14	100 / 100	583 ms	116208 KiB

portals

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1005;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

pair<int, int> L[maxn][maxn];
pair<int, int> R[maxn][maxn];
pair<int, int> U[maxn][maxn];
pair<int, int> D[maxn][maxn];

vector<pair<int, int>> graf[maxn][maxn];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(11);
	cerr << fixed << setprecision(6);

	int n, m;
	cin >> n >> m;

	vector<vector<int>> a(n + 2, vector<int>(m + 2));
	int sx, sy, ex, ey;
	for (int i = 1; i <= n; ++i) {
		string in;
		cin >> in;
		for (int j = 1; j <= m; ++j) {
			char c = in[j - 1];
			a[i][j] = (c == '#' ? 0 : 1);
			if (c == 'S') sx = i, sy = j;
			if (c == 'C') ex = i, ey = j;
		}
	}

	vector<vector<int>> wall(n + 2, vector<int>(m + 2));
	queue<pair<int, int>> q;
	for (int i = 0; i <= n + 1; ++i) {
		for (int j = 0; j <= m + 1; ++j) {
			wall[i][j] = (a[i][j] == 0 ? 0 : -1);
			if (a[i][j] == 0) q.push({i, j});
		}
	}

	auto IsCell = [&](int x, int y) {
		return 1 <= x && x <= n && 1 <= y && y <= m;
	};

	while (q.size()) {
		int x = q.front().first, y = q.front().second;
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = x + dx[dir], ny = y + dy[dir];
			if (IsCell(nx, ny) && wall[nx][ny] == -1) {
				wall[nx][ny] = wall[x][y] + 1;
				q.push({nx, ny});
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (j == 1 || a[i][j - 1] == 0) L[i][j] = {i, j};
			else L[i][j] = L[i][j - 1];
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = m; j >= 1; --j) {
			if (j == m || a[i][j + 1] == 0) R[i][j] = {i, j};
			else R[i][j] = R[i][j + 1];
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (i == 1 || a[i - 1][j] == 0) U[i][j] = {i, j};
			else U[i][j] = U[i - 1][j];
		}
	}

	for (int i = n; i >= 1; --i) {
		for (int j = 1; j <= m; ++j) {
			if (i == n || a[i + 1][j] == 0) D[i][j] = {i, j};
			else D[i][j] = D[i + 1][j];
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			graf[i][j].push_back(L[i][j]);
			graf[i][j].push_back(R[i][j]);
			graf[i][j].push_back(U[i][j]);
			graf[i][j].push_back(D[i][j]);
		}
	}

	set<tuple<int, int, int>> que;
	vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9));
	dist[sx][sy] = 0;
	que.insert({0, sx, sy});

	while (que.size()) {
		auto t = *que.begin();
		int d = get<0>(t);
		int x = get<1>(t);
		int y = get<2>(t);
		que.erase(que.begin());

		if (d > dist[x][y]) continue;

		for (int dir = 0; dir < 4; dir++) {
			int nx = x + dx[dir], ny = y + dy[dir];
			if (IsCell(nx, ny) && a[nx][ny] == 1 && dist[nx][ny] > dist[x][y] + 1) {
				dist[nx][ny] = dist[x][y] + 1;
				que.insert({dist[nx][ny], nx, ny});
			}
		}

		for (auto c : graf[x][y]) {
			int nx = c.first;
			int ny = c.second;
			if (dist[nx][ny] > dist[x][y] + wall[x][y]) {
				dist[nx][ny] = dist[x][y] + wall[x][y];
				que.insert({dist[nx][ny], nx, ny});
			}
		}
	}

	int ans = dist[ex][ey];
	cout << (ans == 1e9 ? -1 : ans) << "\n";
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:133:23: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |  int ans = dist[ex][ey];
      |                       ^
portals.cpp:133:19: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |  int ans = dist[ex][ey];
      |                   ^

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