12761 돌다리

BOJ::12761 돌다리

https://www.acmicpc.net/problem/12761

8가지 경우에 대해 bfs로 탐색해 가장 먼저 도착하는게 몇번째인지 찾아주면 된다.

#include <stdio.h>
#include <queue>
using namespace std;
 
bool visited[100001];
int a, b, n, m, cur, time;
 
 
struct Node {
    int cur;
    int time;
    Node(int c, int t) {
        cur = c;
        time = t;
    }
};
 
void bfs(){
    queue<Node> q;
    q.push(Node(n, 0));
    visited[n] = true;
    int dx[] = { 1,-1,a,b,-a,-b,a,b };
    while (!q.empty()) {
        cur = q.front().cur;
        time = q.front().time;
        q.pop();
        if (cur == m) {
            printf("%d\n", time);
            return;
        }
        int next;
        for (int i = 0; i < 8; i++) {
            if (i >= 6) {
                next = cur * dx[i];
            }
            else {
                next = cur + dx[i];
            }
            if (next >= 0 && next <= 100000) {
                if (!visited[next]) {
                    q.push(Node(next, time + 1));
                    visited[next] = true;
                }
            }
        }
    }
}
 
int main() {
    scanf("%d %d %d %d", &a, &b, &n, &m);
    bfs();
}