Submission #15991

#	Time	Username	Problem	Language	Result	Execution time	Memory
15991		myungwoo	Portals (BOI14_portals)	C++14	0 / 100	0 ms	6620 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];
char A[1001][1002];

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

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] = 2e9;
		if (A[i][j] == 'S') sy = i, sx = j;
		if (A[i][j] == 'C') ey = i, ex = j;
	}
	queue <int> que;
	que.push(sy); que.push(sx); D[sy][sx] = 0;
	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) && D[ny][nx] == 2e9)
				D[ny][nx] = D[y][x]+1, que.push(ny), que.push(nx);
			if (!can_move(ny, nx)){
				int ty = y, tx = x;
				for (;;){
					ny = ty+yy[(d+2)%4], nx = tx+xx[(d+2)%4];
					if (!can_move(ny, nx)) break;
					ty = ny, tx = nx;
				}
				if (D[ty][tx] == 2e9)
					D[ty][tx] = D[y][x]+1, que.push(ty), que.push(tx);
			}
		}
	}
	printf("%d\n", D[ey][ex]);
}

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