7562번: 나이트의 이동

Memo

• Queue 안에 좌표 뿐만 아니라 거리까지 저장하기 위해 tuple을 사용했습니다.

Code

제출 날짜

2021/03/25

메모리

2504 KB

시간

24 ms

#include <iostream>
#include <string.h>
#include <queue>
#include <tuple>

#define endl "\\n"

int T, l;
int k_y, k_x;//knight y x
int f_y, f_x;//final y x
int chess[301][301];
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
std::queue<std::tuple<int, int, int> > q;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> T;
}

void solve()
{
	int x,y, m_x, m_y, dist;
	std::cin >> l >> k_y >> k_x >> f_y >> f_x;

	q.push({k_y, k_x, 0});
	chess[k_y][k_x] = 1;
	while(!q.empty())
	{
		y = std::get<0>(q.front());
		x = std::get<1>(q.front());
		dist = std::get<2>(q.front());
		q.pop();
		if (y == f_y && x == f_x)
		{
			std::cout << dist << endl;
			return ;
		}
		for (int i = 0 ; i < 8 ; i++)
		{
			m_y = y + dy[i];
			m_x = x + dx[i];
			if (m_y < 0 || m_y >= l || m_x < 0 || m_x >= l || chess[m_y][m_x])
				continue;
			chess[m_y][m_x] = 1;
			q.push({m_y , m_x, dist + 1});
		}
	}
}

int main()
{
	input();
	while (T--)
	{
		memset(chess, 0, sizeof(chess));
		q = std::queue<std::tuple<int, int, int> >();
		solve();
	}
	return (0);
}