[백준/BOJ] 백준 12761번 : 돌다리

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

12761번: 돌다리

이동할 수 있는 8가지 방법을 고려하여 목적지까지 이동 횟수의 최솟값을 구한다

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int a, b, n, m;
int discovered[100001];
int depth[100001];
int d[8] = { -1,1,0,0,0,0,0,0 };

int Solve(int start, int dest)
{
	discovered[start] = 1;
	depth[start] = 0;

	queue<int>q;
	q.push(start);

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		//목적지에 도착 했을때
		if (here == dest)
			return depth[here];

		for (int i = 0; i < 8; i++)
		{
			int there;

			if (i == 6 || i == 7)
				there = here * d[i];

			else
				there = here + d[i];

			if (there >= 0 && there <= 100000 && discovered[there] == 0)
			{
				discovered[there] = 1;
				depth[there] = depth[here] + 1;

				q.push(there);
			}
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	memset(discovered, 0, sizeof(discovered));
	memset(depth, 0, sizeof(depth));

	cin >> a >> b >> n >> m;

	d[2] = -a;
	d[3] = a;
	d[4] = -b;
	d[5] = b;
	d[6] = a;
	d[7] = b;

	cout << Solve(n, m);

	return 0;
}