제출 #1278133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278133		mdobric	포탈들 (BOI14_portals)	C++20	100 / 100	754 ms	83716 KiB

portals

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

const int maxn = 1005, inf = 1e9;
int n, m;
char c[maxn][maxn];
int iduci[maxn][maxn][4], pocx, pocy, krajx, krajy, bio[maxn][maxn];
set <pair <int, pair <int, int> > > s;
set <pair <int, pair <int, int> > > ::iterator it;
int pomakx[4] = {-1, 1, 0, 0};
int pomaky[4] = {0, 0, -1, 1};

void dijkstra (){
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if ((i != pocx or j != pocy) and c[pocx][pocy] != '#'){
				bio[i][j] = inf;
				s.insert({inf, {i, j}});
			}
		}
	}
	bio[pocx][pocy] = 0;
	s.insert({0, {pocx, pocy}});
	while (!s.empty()){
		it = s.begin();
		int d = it -> first;
		int x = (it -> second).first;
		int y = (it -> second).second;
		s.erase(it);
		for (int i = 0; i < 4; i++){
			int novix = x + pomakx[i];
			int noviy = y + pomaky[i];
			int novid = d + 1;
			if (novix >= 0 and novix < n and noviy >= 0 and noviy < m and c[novix][noviy] != '#' and novid < bio[novix][noviy]){
				s.erase({bio[novix][noviy], {novix, noviy}});
				bio[novix][noviy] = novid;
				s.insert({bio[novix][noviy], {novix, noviy}});
			}
		}
		int mini = inf;
		mini = min(mini, x - iduci[x][y][0] - 1);
		mini = min(mini, iduci[x][y][1] - x - 1);
		mini = min(mini, y - iduci[x][y][2] - 1);
		mini = min(mini, iduci[x][y][3] - y - 1);
		int novix, noviy, novid;
		novid = d + mini + 1;
		novix = iduci[x][y][0] + 1, noviy = y;
		if (novid < bio[novix][noviy]){
			s.erase({bio[novix][noviy], {novix, noviy}});
			bio[novix][noviy] = novid;
			s.insert({bio[novix][noviy], {novix, noviy}});
		}
		novix = iduci[x][y][1] - 1, noviy = y;
		if (novid < bio[novix][noviy]){
			s.erase({bio[novix][noviy], {novix, noviy}});
			bio[novix][noviy] = novid;
			s.insert({bio[novix][noviy], {novix, noviy}});
		}
		novix = x, noviy = iduci[x][y][2] + 1;
		if (novid < bio[novix][noviy]){
			s.erase({bio[novix][noviy], {novix, noviy}});
			bio[novix][noviy] = novid;
			s.insert({bio[novix][noviy], {novix, noviy}});
		}
		novix = x, noviy = iduci[x][y][3] - 1;
		if (novid < bio[novix][noviy]){
			s.erase({bio[novix][noviy], {novix, noviy}});
			bio[novix][noviy] = novid;
			s.insert({bio[novix][noviy], {novix, noviy}});
		}
	}
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> c[i][j];
			if (c[i][j] == 'S') pocx = i, pocy = j;
			if (c[i][j] == 'C') krajx = i, krajy = j;
		}
	}
	for (int j = 0; j < m; j++){
		int prosli = -1;
		for (int i = 0; i < n; i++){
			iduci[i][j][0] = prosli;
			if (c[i][j] == '#') prosli = i;
		}
	}
	for (int j = 0; j < m; j++){
		int prosli = n;
		for (int i = n - 1; i >= 0; i--){
			iduci[i][j][1] = prosli;
			if (c[i][j] == '#') prosli = i;
		}
	}
	for (int i = 0; i < n; i++){
		int prosli = -1;
		for (int j = 0; j < m; j++){
			iduci[i][j][2] = prosli;
			if (c[i][j] == '#') prosli = j;
		}
	}
	for (int i = 0; i < n; i++){
		int prosli = m;
		for (int j = m - 1; j >= 0; j--){
			iduci[i][j][3] = prosli;
			if (c[i][j] == '#') prosli = j;
		}
	}
	dijkstra();
	/*
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cout << bio[i][j] << " ";
		}
		cout << endl;
	}*/
	cout << bio[krajx][krajy] << "\n";

	return 0;
}

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