12761번

12791번 - 돌다리

간단한 BFS문제

나올 수 있는 8가지 경우를 큐에 포함시켜서 문제를 풀면된다.

<정답 코드>

#include<iostream>
#include<queue>
using namespace std;
 
int a, b, n, m;
int dist[100001];
bool check(int now)
{
    return (now <= 100000 && now >= 0 && dist[now]==0);
}
int main()
{
    cin >> a >> b >> n >> m;
 
    
    queue<int> q;
    q.push(n);
    dist[n] = 0;
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        if (now == m)
            break;
 
        if (check(now + 1)) {
            q.push(now + 1);
            dist[now + 1] = dist[now] + 1;    
        }
 
        if (check(now - 1)) {
            q.push(now - 1);
            dist[now - 1] = dist[now] + 1;
        }
        
        if (check(now + a)) {
            q.push(now + a);
            dist[now + a] = dist[now] + 1;
        }
 
        if (check(now - a)) {
            q.push(now - a);
            dist[now - a] = dist[now] + 1;
        }
 
        if (check(now + b)) {
            q.push(now + b);
            dist[now + b] = dist[now] + 1;
        }
 
        if (check(now - b)) {
            q.push(now - b);
            dist[now - b] = dist[now] + 1;
        }
 
        if (check(now * a)) {
            q.push(now * a);
            dist[now * a] = dist[now] + 1;
        }
 
        if (check(now * b)) {
            q.push(now * b);
            dist[now * b] = dist[now] + 1;
        }
    }
 
    cout << dist[m] << endl;
 
    return 0;
}