글 읽기 - 숨바꼭질3 반례를 모르겠습니

dt43111 7년 전 0

안녕하세요

숨바꼭질3 풀고 테케는돌아가는데 오답으로뜹니다

반례를 생각해봤는데 잘 나오지않네요

답변 부탁드리겠습니다 ㅠ

// 숨바꼭질 3
// https://www.acmicpc.net/problem/13549

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int stt, endd;

int vis[200002];

int main()
{

	scanf("%d %d", &stt, &endd);

	queue<pair<int,int>> q; 

	q.push({ stt, 0 });

 
	for (int i = 0; i <= 200002; i++)
		vis[i] = 0;

	int curCost;
	int curInt;

    while (!q.empty())
	{
		curInt = q.front().first; 
		curCost = q.front().second ;
		q.pop();
		 
        // 답일경우 cost출력 후 종료
		if (curInt == endd)
		{
			cout << curCost << endl;
			return 0;
		}

        // 십만이 넘지않으면 *2 해서 q에삽입 ( 0이면 안돌아도될 자원을 낭비하므로 예외처리 )
		if (curInt <= 100000 && vis[curInt * 2] == 0)
		{
			if (curInt != 0)
			{
				vis[curInt * 2] = 1;
				q.push({ curInt * 2, curCost });
			}
		}

        // 십만 이하면 +1하여 q에삽입
		if (curInt <= 100000 && vis[curInt + 1] == 0)
		{
			vis[curInt + 1] = 1;
			q.push({ curInt + 1, curCost + 1 });
		}

        // 1 이상이면 -1하여 q에삽입
		if (curInt >= 1 && vis[curInt - 1] == 0)
		{
			vis[curInt - 1] = 1;
			q.push({ curInt - 1, curCost + 1 });
		}

	}












	return 0;
}

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

문제

문제

출처

ICPC

숨바꼭질3 반례를 모르겠습니

dt43111 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말