글 읽기 - 10875 질문

dong6788 3년 전 0

안녕하세요 풀어보던 중 질문글들을 읽어봐도 예외케이스가 없는 것 같아 질문 남깁니다

알고리즘은 모든 point 들(마지막 invalid(경계선 밖) point 하나 포함) 을 저장한 뒤,

iterate 하며 여태 나왔던 vertical, horizontal segment 들을 pair 로 저장해 두고

종료조건을

1. point 가 invalid 하거나

2. 여태 나왔던 segment들 중 직전 segment 를 제외한 자신과 수직인 segment 와 intersect 하거나

3. 여태 나왔던 segment 들 중 자신과 평행이면서 같은 높이의 segment 와 intersect 할 때

로 설정하여 진행했습니다 (변수형은 long long 으로 했구요)

(처음에 마지막 명령까지 수행 후 직진하여 벽에 충돌한 다음 칸의 점을 넣어줘서 뱀이 자신에 충돌하지 않더라도 1.조건에서 끝나도록 했습니다)

반나절 정도 고민해 봤는데 안 떠올라서 구현 실수인가 의심도 되는데.. 코드가 더럽지만 한번 확인해주시면 넘나 감사할 것 같습니다 ㅠㅠ

#include <iostream>
#include <algorithm>

#define ll long long
#define int ll

using namespace std;


#define max(A,B) (((A)>(B)) ? (A) : (B))
#define min(A,B) (((A)<(B)) ? (A) : (B))
#define abs(A) (((A)<0) ? (-(A)):(A))
#define celi(A,B) (((A)+(B)-1) / (B))
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)

// (1,0) (0,1) (-1,0) (0,-1), L : +1 / R : -1
int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1};
int xp[1010], yp[1010], L, hcnt, vcnt;

pair<pair<int, int>, int> hor[1010]; // horizontel seg (y const)
pair<int, pair<int, int>> ver[1010]; // vertical seg (x const)

bool isvalid(int x, int y) {
	return -L <= x && x <= L && -L <= y && y <= L;
}

bool intersect(pair<pair<int, int>, int> hor_seg, pair<int, pair<int, int>> ver_seg) {
	int x = ver_seg.first, y = hor_seg.second;
	if (hor_seg.first.first <= x && x <= hor_seg.first.second
		&& ver_seg.second.first <= y && y <= ver_seg.second.second) return true;
	return false;
}

void solve(int tc) {
	int n, length, cd = 0, cx = 0, cy = 0;
	cin >> L >> n;
	int invalid_val = 4 * L;
	string Dir;
	xp[0] = yp[0] = 0;
	rep1(i, n) {
		cin >> length >> Dir;
		cx += xdir[cd] * length;
		cy += ydir[cd] * length;
		xp[i] = cx;
		yp[i] = cy;
		//printf("(%lld, %lld), dir %lld\n", cx, cy, cd);
		if (Dir[0] == 'L') cd++;
		else cd--;
		cd += 4;
		cd = cd % 4;
	}
	// revision 1. Add final invalid point to consider last segment intersecting case
	n++;
	xp[n] = min(L+1, max(-(L+1), cx + (L+1) * xdir[cd]));
	yp[n] = min(L+1, max(-(L+1), cy + (L+1) * ydir[cd]));
	// It need to get out of border to be invalid, so i used L+1 instead of L


	//rep1(i, n) {
	//	if (!isvalid(xp[i], yp[i])) {
	//		n = i;
	//		break;
	//	}
	//}

	int time = 0, mintime;
	hcnt = vcnt = 0;
	rep1(i, n) {
		//printf("before (%lld, %lld) loop, %lld\n", xp[i], yp[i], time);
		mintime = invalid_val;

		if (!isvalid(xp[i], yp[i])) {
			mintime = 1; // in this case snake need to go out of borderline, so need corrction
			if (xp[i] > L) mintime += L - xp[i - 1];
			else if (xp[i] < -L) mintime += xp[i - 1] + L;
			else if (yp[i] > L) mintime += L - yp[i - 1];
			else if (yp[i] < -L) mintime += yp[i - 1] + L;
			//printf("(%lld %lld) is not valid, mintime %lld\n", xp[i], yp[i], mintime);
		}

		if (i % 2 == 1) {
			// horizontal , y[i-1] == y[i]
			// make sure segment's second is always bigger than first
			hor[hcnt] = make_pair(make_pair(min(xp[i-1], xp[i]), max(xp[i-1], xp[i])), yp[i]);
			rep(j, vcnt - 1) {
				// compare all appeared vertical segs without right before one
				if (intersect(hor[hcnt], ver[j])) mintime = min(mintime, abs(ver[j].first - xp[i-1]));
			}
			rep(j, hcnt) {
				//revision 2. need to check all parallel segs if y is same
				if (hor[j].second != yp[i]) continue;
				int ts = hor[j].first.first, te = hor[j].first.second;
				//check if same-height parallel segs crossing
				if(xp[i-1] < ts && ts <= xp[i]) mintime = min(mintime, ts - xp[i - 1]);
				if(xp[i] < te && te <= xp[i-1]) mintime = min(mintime, xp[i - 1] - te);
			}
			if (mintime < invalid_val) {
				cout << time + mintime << "\n";
				return;
			}
			hcnt++;
			time += abs(xp[i] - xp[i - 1]);
		}
		else {
			// vertical , x[i-1] == x[i]
			ver[vcnt] = make_pair(xp[i], make_pair(min(yp[i - 1], yp[i]), max(yp[i - 1], yp[i])));
			rep(j, hcnt - 1) {
				// compare all appeared horizontal segs without right before one
				if (intersect(hor[j], ver[vcnt])) mintime = min(mintime, abs(hor[j].second - yp[i-1]));
			}
			rep(j, vcnt) {
				//revision 2. need to check all parallel segs if x is same
				if (ver[j].first != xp[i]) continue;
				int ts = ver[j].second.first, te = ver[j].second.second;
				//check if same-x-parallel segs crossing
				if (yp[i - 1] < ts && ts <= yp[i]) mintime = min(mintime, ts - yp[i - 1]);
				if (yp[i] < te && te <= yp[i - 1]) mintime = min(mintime, yp[i - 1] - te);
			}
			if (mintime < invalid_val) {
				cout << time + mintime << "\n";
				return;
			}
			vcnt++;
			time += abs(yp[i] - yp[i - 1]);
		}
	}

	// after revision 1, it gurentee above case has at least 1 invalid case, below part will not visited
	//printf("This Part Will Not Be Visited\n");

	time += 1; // border out correction
	if (cd == 0) time += L - cx;
	else if (cd == 1) time += L - cy;
	else if (cd == 2) time += cx + L;
	else if (cd == 3) time += cy + L;
	
	cout << time << "\n";

}
signed main() {
	int T = 1, tc;
//	cin >> T;
	for (tc = 1; tc <= T; tc++) solve(tc);
}

3587jjh 3년 전 1

제 코드와 비교해서 랜덤으로 반례 데이터를 만들어보았습니다

<입력>

6 2
2 L
5 L

<ans>

<wa>

dong6788 3년 전 0

아.. 마지막 invalid point 만들 때 한 변의 길이가 L이라고 착각하여 진행방향으로 L+1 보내주면 밖으로 나갈 줄 알았는데 2L+1 을 더해줘야 하는 부분에서 실수가 났네요

55, 56 라인의 각각 3번째 L+1 부분을 2L+1 로 고쳐주니 해결되었습니다. 반례 찾아주셔서 감사합니다!!

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

문제

문제

출처

ICPC

10875 질문

dong6788 3년 전 0

3587jjh 3년 전 1

dong6788 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말