728x90
https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ...
www.acmicpc.net
#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int testCase;
cin >> testCase;
for (int t = 0; t < testCase; t++) {
int l;
cin >> l;
int nowRow, nowCol;
int destRow, destCol;
cin >> nowRow >> nowCol >> destRow >> destCol;
int count;
tuple<int, int, int> now = make_tuple(nowRow, nowCol, 0);
queue<tuple<int, int, int>> q;
vector<vector<bool>> visited(l, vector<bool>(l));
q.push(now);
while (!q.empty()) {
tuple<int, int, int> cur = q.front();
q.pop();
if (!visited[get<0>(cur)][get<1>(cur)]) {
visited[get<0>(cur)][get<1>(cur)] = true;
if (get<0>(cur) == destRow && get<1>(cur) == destCol) {
count = get<2>(cur);
break;
}
if (get<0>(cur) - 2 >= 0 && get<1>(cur) - 1 >= 0 && !visited[get<0>(cur) - 2][get<1>(cur) - 1]) {
q.push(make_tuple(get<0>(cur) - 2, get<1>(cur) - 1, get<2>(cur) + 1));
}
if (get<0>(cur) - 2 >= 0 && get<1>(cur) + 1 < l && !visited[get<0>(cur) - 2][get<1>(cur) + 1]) {
q.push(make_tuple(get<0>(cur) - 2, get<1>(cur) + 1, get<2>(cur) + 1));
}
if (get<0>(cur) - 1 >= 0 && get<1>(cur) - 2 >= 0 && !visited[get<0>(cur) - 1][get<1>(cur) - 2]) {
q.push(make_tuple(get<0>(cur) - 1, get<1>(cur) - 2, get<2>(cur) + 1));
}
if (get<0>(cur) - 1 >= 0 && get<1>(cur) + 2 < l && !visited[get<0>(cur) - 1][get<1>(cur) + 2]) {
q.push(make_tuple(get<0>(cur) - 1, get<1>(cur) + 2, get<2>(cur) + 1));
}
if (get<0>(cur) + 1 < l && get<1>(cur) - 2 >= 0 && !visited[get<0>(cur) + 1][get<1>(cur) - 2]) {
q.push(make_tuple(get<0>(cur) + 1, get<1>(cur) - 2, get<2>(cur) + 1));
}
if (get<0>(cur) + 1 < l && get<1>(cur) + 2 < l && !visited[get<0>(cur) + 1][get<1>(cur) + 2]) {
q.push(make_tuple(get<0>(cur) + 1, get<1>(cur) + 2, get<2>(cur) + 1));
}
if (get<0>(cur) + 2 < l && get<1>(cur) - 1 >= 0 && !visited[get<0>(cur) + 2][get<1>(cur) - 1]) {
q.push(make_tuple(get<0>(cur) + 2, get<1>(cur) - 1, get<2>(cur) + 1));
}
if (get<0>(cur) + 2 < l&& get<1>(cur) + 1 < l && !visited[get<0>(cur) + 2][get<1>(cur) + 1]) {
q.push(make_tuple(get<0>(cur) + 2, get<1>(cur) + 1, get<2>(cur) + 1));
}
}
}
cout << count << '\n';
}
return 0;
}
728x90
'알고리즘 문제' 카테고리의 다른 글
[백준] 4504번 배수 찾기 (0) | 2020.02.28 |
---|---|
[백준] 1919번 애너그램 만들기 (0) | 2020.02.28 |
[백준] 1145번 적어도 대부분의 배수 (0) | 2020.02.25 |
[백준] 2523번 별 찍기 - 13 (0) | 2020.02.25 |
[백준] 2522번 별 찍기 - 12 (0) | 2020.02.24 |