Submission #943229

#	Time	Username	Problem	Language	Result	Execution time	Memory
943229		siewjh	Portals (BOI14_portals)	C++17	100 / 100	547 ms	175120 KiB

portals

#include <bits/stdc++.h>
using namespace std;
const int MAXR = 1005;
const int MAXN = 1000005;
const int inf = 1e9;
char grid[MAXR][MAXR];
int dtw[MAXR][MAXR], dist[MAXN];
vector<pair<int, int>> adj[MAXN];
int rows, cols, rmove[] = {1, -1, 0, 0}, cmove[] = {0, 0, 1, -1};
int gind(int r, int c){
	return (r - 1) * cols + (c - 1);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> rows >> cols;
	int st, en;
	for (int i = 0; i <= rows + 1; i++)
		for (int j = 0; j <= cols + 1; j++)
			grid[i][j] = '#';
	for (int i = 1; i <= rows; i++)
		for (int j = 1; j <= cols; j++){
			char ch; cin >> ch;
			if (ch == '#') grid[i][j] = '#';
			else{
				grid[i][j] = '.';
				if (ch == 'S') st = gind(i, j);
				else if (ch == 'C') en = gind(i, j);
			}
		}
	queue<pair<int, int>> q;
	memset(dtw, -1, sizeof(dtw));
	for (int r = 1; r <= rows; r++)
		for (int c = 1; c <= cols; c++){
			if (grid[r][c] == '#') continue;
			for (int k = 0; k < 4; k++){
				int nr = r + rmove[k], nc = c + cmove[k];
				if (grid[nr][nc] == '#'){
					dtw[r][c] = 1;
					q.push({r, c});
					break;
				}
			}
		}
	while (!q.empty()){
		int r, c; tie(r, c) = q.front(); q.pop();
		for (int k = 0; k < 4; k++){
			int nr = r + rmove[k], nc = c + cmove[k];
			if (grid[nr][nc] != '#' && dtw[nr][nc] == -1){
				dtw[nr][nc] = dtw[r][c] + 1;
				q.push({nr, nc});
			}
		}
	}
	for (int r = 1; r <= rows; r++)
		for (int c = 1; c <= cols; c++){
			if (grid[r][c] == '#') continue;
			for (int k = 0; k < 4; k++){
				int nr = r + rmove[k], nc = c + cmove[k];
				if (grid[nr][nc] == '.'){
					adj[gind(r, c)].push_back({gind(nr, nc), 1});
					adj[gind(nr, nc)].push_back({gind(r, c), 1});
				}
			}
		}
	for (int r = 1; r <= rows; r++){
		int pw = 0;
		for (int c = 1; c <= cols; c++){
			if (grid[r][c] == '#') pw = c;
			else adj[gind(r, c)].push_back({gind(r, pw + 1), dtw[r][c]});
		}
		pw = cols + 1;
		for (int c = cols; c >= 1; c--){
			if (grid[r][c] == '#') pw = c;
			else adj[gind(r, c)].push_back({gind(r, pw - 1), dtw[r][c]});
		}
	}
	for (int c = 1; c <= cols; c++){
		int pw = 0;
		for (int r = 1; r <= rows; r++){
			if (grid[r][c] == '#') pw = r;
			else adj[gind(r, c)].push_back({gind(pw + 1, c), dtw[r][c]});
		}
		pw = rows + 1;
		for (int r = rows; r >= 1; r--){
			if (grid[r][c] == '#') pw = r;
			else adj[gind(r, c)].push_back({gind(pw - 1, c), dtw[r][c]});
		}
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, st});
	for (int i = 0; i < MAXN; i++) dist[i] = inf;
	dist[st] = 0;
	while (!pq.empty()){
		int x, d; tie(d, x) = pq.top(); pq.pop();
		if (dist[x] != d) continue;
		if (x == en){
			cout << d;
			return 0;
		}
		for (auto [nn, nd] : adj[x]){
			if (dist[nn] > d + nd){
				dist[nn] = d + nd;
				pq.push({dist[nn], nn});
			}
		}
	}
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:93:11: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |  dist[st] = 0;
      |  ~~~~~~~~~^~~
portals.cpp:97:3: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |   if (x == en){
      |   ^~

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