백준 12761번 돌다리

문제

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A,B 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배나 B배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

입력

입력의 첫 줄에 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현재 위치 M이 주어진다. (단, 2≤A,B≤30 이고  0≤N,M≤100,000)

출력

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.

 

 

 

아이디어는 맞았는데 런타임 오류의 발생했었음 여러함수의 반복 호출이 원인이라 생각했지만, 아닌걸로 판명 그냥 내가 뭔가 잘못쓴걸로.... 이해는 안되지만....

 

 

 

 

 

 

 

 

 

 

 

 

#include <iostream>
#include <queue>


using namespace std;

bool visit[100001];
int A,B,N,M;

queue<pair<int, int> > que;





int main(void)
{


 ios_base::sync_with_stdio(0);

cin >> A >> B>> N >> M;

que.push(make_pair(N,0));
visit[N] = true;

while(!que.empty())
{
   int current = que.front().first;
   int count = que.front().second;
que.pop();

if(current == M)
{
cout << count <<endl;
break;
    }
    else{


if(current*A <= 100000 && current*A >= 0 && !visit[current*A])
{
visit[current*A] = true;
que.push(make_pair(current*A , count+1));
}
if(current*B <= 100000 && current*B >= 0 && !visit[current*B])
{
visit[current*B] = true;
que.push(make_pair(current*B , count+1));
}
if(current+A <= 100000 && current+A >= 0 && !visit[current+A])
{
visit[current+A] = true;
que.push(make_pair(current+A , count+1));
}
if(current+B <= 100000 && current+B >= 0 && !visit[current+B])
{
visit[current+B] = true;
que.push(make_pair(current+B , count+1));
}
if(current-A <= 100000 && current-A >= 0 && !visit[current-A])
{
visit[current-A] = true;
que.push(make_pair(current-A , count+1));
}
if(current-B <= 100000 && current-B >= 0 && !visit[current-B])
{
visit[current-B] = true;
que.push(make_pair(current-B , count+1));
}
if(current+1 <= 100000 && current+1 >= 0 && !visit[current+1])
{
visit[current+1] = true;
que.push(make_pair(current+1 , count+1));
}
if(current-1 <= 100000 && current-1 >= 0 && !visit[current-1])
{
visit[current-1] = true;
que.push(make_pair(current-1 , count+1));
}







        }












}






}