Submission #15997

#	Time	Username	Problem	Language	Result	Execution time	Memory
15997		myungwoo	Portals (BOI14_portals)	C++14	100 / 100	245 ms	31696 KiB

portals

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

int yy[]={-1, 0, 1, 0}, xx[]={0, 1, 0, -1};
int N, M;
int sy, sx, ey, ex;
int D[1001][1001], E[1001][1001], F[1002][1002][4];
char A[1001][1002];

struct Z{
	int d, y, x;
	bool operator < (const Z &ot)const{
		return d > ot.d;
	}
};

inline bool can_move(int y, int x){ return !(y < 1 || y > N || x < 1 || x > M || A[y][x] == '#'); }

void portal_bfs()
{
	queue <int> que;
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) if (can_move(i, j)){
		bool sw = 0;
		for (int d=0;d<4;d++){
			int ny = i+yy[d], nx = j+xx[d];
			if (!can_move(ny, nx)){ sw = 1; break; }
		}
		if (!sw) continue;
		E[i][j] = 0; que.push(i), que.push(j);
	}
	while (!que.empty()){
		int y = que.front(); que.pop();
		int x = que.front(); que.pop();
		for (int d=0;d<4;d++){
			int ny = y+yy[d], nx = x+xx[d];
			if (!can_move(ny, nx)) continue;
			if (E[ny][nx] == 2e9)
				E[ny][nx] = E[y][x]+1, que.push(ny), que.push(nx);
		}
	}
}

int main()
{
	scanf("%d%d", &N, &M);
	for (int i=1;i<=N;i++) scanf("%s", A[i]+1);
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
		D[i][j] = E[i][j] = 2e9;
		if (A[i][j] == 'S') sy = i, sx = j;
		if (A[i][j] == 'C') ey = i, ex = j;
	}
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
		F[i][j][0] = A[i][j] == '#' ? 0 : F[i-1][j][0]+1;
		F[i][j][3] = A[i][j] == '#' ? 0 : F[i][j-1][3]+1;
	}
	for (int i=N;i;i--) for (int j=M;j;j--){
		F[i][j][1] = A[i][j] == '#' ? 0 : F[i][j+1][1]+1;
		F[i][j][2] = A[i][j] == '#' ? 0 : F[i+1][j][2]+1;
	}
	portal_bfs();
	priority_queue <Z> que;
	D[sy][sx] = 0; que.push({0, sy, sx});
	while (!que.empty()){
		Z q = que.top(); que.pop();
		if (q.d != D[q.y][q.x]) continue;
		for (int d=0;d<4;d++){
			int y = q.y+yy[d], x = q.x+xx[d];
			if (!can_move(y, x)) continue;
			if (D[y][x] > q.d+1)
				D[y][x] = q.d+1, que.push({D[y][x], y, x});
			y = q.y + yy[d] * (F[q.y][q.x][d]-1);
			x = q.x + xx[d] * (F[q.y][q.x][d]-1);
			if (D[y][x] > q.d+E[q.y][q.x]+1)
				D[y][x] = q.d+E[q.y][q.x]+1, que.push({D[y][x], y, x});
		}
	}
	printf("%d\n", D[ey][ex]);
}

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