제출 #412515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
412515		rqi	포탈들 (BOI14_portals)	C++14	100 / 100	400 ms	46584 KiB

portals

#include <bits/stdc++.h>
using namespace std;
 
typedef vector<int> vi;
typedef long long ll;
typedef long double db;
typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second
#define pb push_back

#define sz(x) (int)(x).size()
 
const int MOD = 1e9+7;
const int mx = 1005;

const vi dx = vi{1, 0, -1, 0};
const vi dy = vi{0, 1, 0, -1};

int R, C;
bool wall[mx][mx];
pi hit[mx][mx][4];

void setHit(int i, int j, int d){
	if(hit[i][j][d] != mp(-1, -1)) return;
	if(wall[i+dx[d]][j+dy[d]]){
		hit[i][j][d] = mp(i, j);
		return;
	}
	setHit(i+dx[d], j+dy[d], d);
	hit[i][j][d] = hit[i+dx[d]][j+dy[d]][d];
}

int wall_dist[mx][mx];
int dist[mx][mx];
 
int main(){
	cin.tie(0)->sync_with_stdio(0);
	pi start_pos;
	pi end_pos;
	cin >> R >> C;
	for(int i = 0; i <= R+1; i++){
		wall[i][0] = wall[i][C+1] = 1;
	}
	for(int i = 0; i <= C+1; i++){
		wall[0][i] = wall[R+1][i] = 1;
	}


	for(int i = 1; i <= R; i++){
		string s;
		cin >> s;
		for(int j = 1; j <= C; j++){
			if(s[j-1] == '#'){
				wall[i][j] = 1;
			}
			else if(s[j-1] == 'S'){
				start_pos = mp(i, j);
			}
			else if(s[j-1] == 'C'){
				end_pos = mp(i, j);
			}
		}
	}

	for(int d = 0; d < 4; d++){
		for(int i = 0; i <= R+1; i++){
			for(int j = 0; j <= C+1; j++){
				hit[i][j][d] = mp(-1, -1);
			}
		}
		for(int i = 0; i <= R+1; i++){
			for(int j = 0; j <= C+1; j++){
				if(!wall[i][j]){
					setHit(i, j, d);
				}
			}
		}
	}

	queue<pi> q;
	for(int i = 0; i <= R+1; i++){
		for(int j = 0; j <= C+1; j++){
			wall_dist[i][j] = MOD;
			if(wall[i][j]){
				wall_dist[i][j] = 0;
				q.push(mp(i, j));
			}
		}
	}
	while(sz(q)){
		pi pos = q.front();
		q.pop();
		for(int d = 0; d < 4; d++){
			pi new_pos = mp(pos.f+dx[d], pos.s+dy[d]);
			if(new_pos.f < 0 || new_pos.f > R+1 || new_pos.s < 0 || new_pos.s > C+1) continue;
			int new_dist = wall_dist[pos.f][pos.s]+1;
			if(wall_dist[new_pos.f][new_pos.s] <= new_dist) continue;
			wall_dist[new_pos.f][new_pos.s] = new_dist;
			q.push(new_pos);
		}
	}

	// for(int i = 0; i <= R+1; i++){
	// 	for(int j = 0; j <= C+1; j++){
	// 		cout << wall_dist[i][j] << " ";
	// 	}
	// 	cout << "\n";
	// }

	priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
	for(int i = 0; i <= R+1; i++){
		for(int j = 0; j <= C+1; j++){
			dist[i][j] = MOD;
		}
	}
	dist[start_pos.f][start_pos.s] = 0;
	pq.push(mp(0, start_pos));
	while(sz(pq)){
		int test_dist = pq.top().f; 
		pi pos = pq.top().s;
		pq.pop();
		if(dist[pos.f][pos.s] < test_dist) continue;
		if(pos == end_pos){
			cout << test_dist << "\n";
			exit(0);
		}
		for(int d = 0; d < 4; d++){
			pi new_pos = mp(pos.f+dx[d], pos.s+dy[d]);
			if(wall[new_pos.f][new_pos.s]) continue;
			int new_dist = dist[pos.f][pos.s]+1;
			if(dist[new_pos.f][new_pos.s] <= new_dist) continue;
			dist[new_pos.f][new_pos.s] = new_dist;
			pq.push(mp(dist[new_pos.f][new_pos.s], new_pos));
		}
		for(int d = 0; d < 4; d++){
			pi new_pos = hit[pos.f][pos.s][d];
			if(wall[new_pos.f][new_pos.s]) continue;
			int new_dist = dist[pos.f][pos.s]+wall_dist[pos.f][pos.s];
			if(dist[new_pos.f][new_pos.s] <= new_dist) continue;
			dist[new_pos.f][new_pos.s] = new_dist;
			pq.push(mp(dist[new_pos.f][new_pos.s], new_pos));
		}
	}
	assert(false);
}

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