제출 #1278129

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

portals

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

const int maxn = 1005;
int n, m;
char c[maxn][maxn];
int iduci[maxn][maxn][4], pocx, pocy, krajx, krajy, bio[maxn][maxn];
queue <pair <int, int> > q;
int pomakx[4] = {-1, 1, 0, 0};
int pomaky[4] = {0, 0, -1, 1};

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;
		}
	}
	memset(bio, -1, sizeof bio);
	bio[pocx][pocy] = 0;
	q.push({pocx, pocy});
	while (!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++){
			int novix = pomakx[i] + x;
			int noviy = pomaky[i] + y;
			if (novix >= 0 and novix < n and noviy >= 0 and noviy < m and bio[novix][noviy] == -1 and c[novix][noviy] != '#'){
				q.push({novix, noviy});
				bio[novix][noviy] = bio[x][y] + 1;
			}
		}
		if (x == 0 or c[x - 1][y] == '#' or x == n - 1 or c[x + 1][y] == '#' or y == 0 or c[x][y - 1] == '#' or y == m - 1 or c[x][y + 1] == '#'){
			int novix = iduci[x][y][1] - 1;
			int noviy = y;
			if (bio[novix][noviy] == -1){
				q.push({novix, noviy});
				bio[novix][noviy] = bio[x][y] + 1;
			}
			novix = iduci[x][y][0] + 1;
			noviy = y;
			if (bio[novix][noviy] == -1){
				q.push({novix, noviy});
				bio[novix][noviy] = bio[x][y] + 1;
			}
			novix = x;
			noviy = iduci[x][y][3] - 1;
			if (bio[novix][noviy] == -1){
				q.push({novix, noviy});
				bio[novix][noviy] = bio[x][y] + 1;
			}
			novix = x;
			noviy = iduci[x][y][2] + 1;
			if (bio[novix][noviy] == -1){
				q.push({novix, noviy});
				bio[novix][noviy] = bio[x][y] + 1;
			}
			
		}
	}
	cout << bio[krajx][krajy] << "\n";

	return 0;
}

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