Submission #789543

#	Time	Username	Problem	Language	Result	Execution time	Memory
789543		bane	Portals (BOI14_portals)	C++17	100 / 100	248 ms	46476 KiB

portals

#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

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

int dist[1005][1005], nearest_wall[1005][1005];
char grid[1005][1005];
pair<int,int>Portals[1005][1005][4];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	n += 2, m += 2;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (i == 0 || j == 0 || j == m - 1 || i == n - 1){
				grid[i][j] = '#';
				continue;
			}
			cin >> grid[i][j];
		}
	}
	
	pair<int,int>start = {-1,-1};
	pair<int,int>cake = {-1,-1};
	
	queue<pair<int,int>>q;	
	for (int i = 0; i <= 1000; i++){
		for (int j = 0; j <= 1000; j++){
			nearest_wall[i][j] = (int)1e9;
		}
	}
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (grid[i][j] == 'S'){
				start = {i,j};
			}
			if (grid[i][j] == 'C'){
				cake = {i,j};
			}
			if (grid[i][j]== '#'){
				nearest_wall[i][j] = 0;
				q.push({i,j});
			}
		}
	}

	while(!q.empty()){
		auto [x,y] = q.front();
		q.pop();
		for (int dir = 0; dir < 4; dir++){
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < n && nx >= 0 && ny < m && ny >= 0){
				if (nearest_wall[nx][ny] > nearest_wall[x][y] + 1){
					q.push({nx,ny});
					nearest_wall[nx][ny] = nearest_wall[x][y] + 1;
				}
			}
		}
	}
	for (int j = 0; j < m; j++){
		//go down - > go up with man
		int highest = 0;
		for (int i = 0; i < n; i++){
			if (grid[i][j] == '#'){
				highest = i;
			}
			Portals[i][j][0] = {highest + 1,j};
		}
		highest = n - 1;
		for (int i = n - 1; i>=0; i--){
			if (grid[i][j] == '#'){
				highest = i;
			}
			Portals[i][j][1] = {highest - 1,j};
		}
	}

	for (int i = 0; i < n; i++){
		//go right - > go left with man
		int Lowest = 0;
		for (int j = 0; j < m; j++){
			if (grid[i][j] == '#'){
				Lowest = j;
			}
			Portals[i][j][3] = {i, Lowest + 1};
		}
		Lowest = m - 1;
		for (int j = m - 1; j>=0; j--){
			if (grid[i][j] == '#'){
				Lowest = j;
			}
			Portals[i][j][2] = {i,Lowest - 1};
		}
	}

	priority_queue<pair<int,pair<int,int>>>dijkstra;
	dijkstra.push({0,{start.first,start.second}});

	for (int i = 0; i <= 1000; i++){
		for (int j = 0; j <= 1000; j++){
			dist[i][j] = (int)1e9;
		}
	}
	dist[start.first][start.second] = 0;

	while(!dijkstra.empty()){
		int d = -dijkstra.top().first;
		auto [x,y] = dijkstra.top().second;
		dijkstra.pop();
		if (d != dist[x][y]){
			continue;
		}

		for (int dir = 0; dir < 4; dir++){
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < n && nx >= 0 && ny < m && ny >= 0){
				if (grid[nx][ny] != '#'){
					if (dist[nx][ny] > d + 1){
						dijkstra.push({-d-1, {nx,ny}});
						dist[nx][ny] = d + 1;
					}
				}
			}

			//teleport
			nx = Portals[x][y][dir].first;
			ny = Portals[x][y][dir].second;

			if (dist[nx][ny] > nearest_wall[x][y] + d){
				if (grid[nx][ny] != '#'){
					dist[nx][ny] = d + nearest_wall[x][y];
					dijkstra.push({-dist[nx][ny], {nx,ny}});
				}
			}
		}
	}

	cout << dist[cake.first][cake.second] << '\n';

	return 0;
}

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