글 읽기 - (bfs)숨바꼭질 5 질문드립니다.

omh9876 2년 전 0

t초 일때 어떤 지점을 언니가 방문했다면 t+2,t+4,t+6... 초에도 방문할 수 있다는 질문게시판의 글을 보고

원래 방문했던 지점은 방문하지 않는 평범한 bfs에 동생이 언니가 방문했던 지점을 방문하면

동생이 방문했을 때의 시간에서 언니가 방문했을 때의 시간을 빼서 해당 수가 짝수면 거기서 만날 수 있는 것으로 보고

풀었습니다.

게시판에 있는 반례들 모두 맞습니다만 틀렸다고 나옵니다.

어디가 문제일까요?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
long n, m;
typedef struct a {
	long x;
	long cnt;
}kk;
long map[1001000] = { 0 };
long vis[1001000] = { 0 };
kk q[1001000] = { 0 };
long ans = 10000000, ans2 = 0, head = 0, top = -1;
void bfs() {
	q[++top].x = n;
	q[top].cnt = 0;
	long tx, ttx, tcnt = q[head].cnt;
	long kt;
	while (top - head != -1) {
		tcnt = q[head].cnt;
		ttx = q[head++].x;
		kt = m + (tcnt + 2) * (tcnt + 1) / 2;
			if (vis[kt] != 0) {
				if ( (tcnt+1-vis[kt])%2==0) {
					ans = tcnt+1;
					return;
				}
			}
			//prlongf("%d %d\n ", ttx, tcnt);
		for (long i = 0; i < 3; i++) {//이동
			if (i == 0)
				tx = ttx + 1;
			else if (i == 1)
				tx = ttx - 1;
			else {
				tx = ttx * 2;

			}
			if (tx <= -1)//범위 넘어가면 무시
				continue;
			if (tx >500000)
				continue;
		
		//	printf("%d %d %d %d\n", tcnt+1, tx, ttx, m + (tcnt + 1) * (tcnt + 2) / 2);
			if (m+(tcnt + 2) * (tcnt + 1)/2 > 500000) {
				printf("-1");//동생의 위치가 500000이 넘으면 종료
				exit(0);

			}
			if (tx == m+(tcnt+1)*(tcnt+2)/2) {//동생 찾음
				ans = tcnt + 1;
				return;			//종료
			}

			if (vis[tx] == 0) {//위에서 내가 이미 방문한 점을 동생이
				//방문하면 그에 따른 처리를 해주었으므로 한 번 방문한 곳은
				//다시 방문 못하게 함
				q[++top].x = tx;
				q[top].cnt = tcnt + 1;
				vis[tx] = tcnt + 1;
			}
		}

	}

	printf("-1");//다 돌았는데 없다? 종료
	exit(0);
}

int main() {
	scanf(" %ld", &n);
	scanf(" %ld", &m);
	if (n == m)
	{
		printf("0");
		return 0;
	}
	bfs();
	printf("%ld", ans);
	return 0;
}

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

문제

문제

출처

ICPC

(bfs)숨바꼭질 5 질문드립니다.

omh9876 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말