글 읽기 - 암벽등반 틀린부분 좀 찾아주세요

wonjung1618 5년 전 0

5%에서 광속으로 틀렸다고 뜨는데.... 못찾겠어요 ㅠ

#include <stdio.h>

int N, T;

int chk[50100];
int s[200100], e[200100];
int ymax, xmax, ylo;
int ans;

typedef struct{
	int x;
	int y;
}ss;

typedef struct {
	int loc;
	int via;
}qq;

qq q[50100];
ss cli[50100];

void qs(int low, int high)
{
	int i, j, mid;
	ss temp;

	if (low < high) {
		mid = (low + high) / 2;
		i = low - 1;
		j = high + 1;

		while (1)
		{
			while (cli[++i].y < cli[mid].y || cli[i].y == cli[mid].y && cli[i].x < cli[mid].x);
			while (cli[--j].y > cli[mid].y || cli[j].y == cli[mid].y && cli[j].x > cli[mid].x);
			if (i >= j)break;

			temp = cli[i]; cli[i] = cli[j]; cli[j] = temp;
		}
		qs(low, i-1);
		qs(j+1, high);

	}
}

int process(int low, int high, int x)
{
	int mid;
	if (low <= high) {
		mid = (low + high) / 2;
		if (cli[mid].x > x) return process(low, mid - 1, x);
		else if (cli[mid].x < x) return process(mid + 1, high, x);
		else return mid;
	}

	return -1;  
}


int main(void)
{
	int i, j;
	int st, ed;

	scanf("%d %d", &N, &T);

	for (i = 1; i <= N; i++) {
		scanf("%d %d", &cli[i].x, &cli[i].y);
		e[cli[i].y]++;
		if (cli[i].y > ymax)ymax = cli[i].y;
		if (cli[i].x > xmax)xmax = cli[i].x;
	}

	qs(1, N);

	s[0]++;

	for (i = 1; i <= ymax; i++) {
		s[i] = e[i - 1] + 1;
		e[i] += e[i - 1];
	}

	st = -1; ed = -1;

	q[++st].loc = 0;
	q[st].via = 0;
	chk[q[st].loc] = 1;

	while (st != ed)
	{
		++ed;

		ylo = q[ed].loc;

		if (cli[ylo].y == T) {
			printf("%d", q[ed].via);
			return 0;
		}

		for (i = cli[ylo].y - 2; i <= cli[ylo].y + 2; i++) {
			if (i < 0)continue;
			if (i > ymax)continue;
			if (s[i] > e[i])continue;

			for (j = cli[ylo].x - 2; j <= cli[ylo].x + 2; j++) {
				if (j < 0)continue;
				if (j > xmax)continue;
				ans=process(s[i], e[i], j);
				if (ans != -1 && chk[ans]!=1) {
					q[++st].loc = ans;
					q[st].via = q[ed].via + 1;
					chk[q[st].loc] = 1;
				}
			}

		}			
	}

	printf("-1");

	return 0;
}

chogahui05 5년 전 0

전 그래프를 구축하고 bfs 돌렸습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

암벽등반 틀린부분 좀 찾아주세요

wonjung1618 5년 전 0

chogahui05 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말