https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
쉽당
#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
#include<cmath>
using namespace std;
void Prints(vector<vector<char>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j] << ",";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j] << ",";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j] << ",";
}
cout << endl;
}
cout << endl;
}
struct Point {
int i;
int j;
int cnt=0;
};
struct Data {
int index;
int cnt = 0;
int gc = 1;
};
int main() {
int T;
cin >> T;
vector<int>gCount;
for (int z = 0; z < T; z++) {
int n;
cin >> n;
vector<int>tmpMaps(n, 0);
vector<bool>tmpbVisited(n,false);
vector<vector<int>>maps(n,tmpMaps);
vector<vector<bool>>bVisitied(n, tmpbVisited);
Point knight;
cin >> knight.i;
cin >> knight.j;
Point end;
cin >> end.i;
cin >> end.j;
queue<Point>q;
q.push(knight);
int diri[] = { -1,1,1,-1,2,2,-2,-2 };
int dirj[] = { 2,2,-2,-2,1,-1,-1,1 };
bool bEnd = false;
int count = 0;
while (!q.empty()) {
Point start=q.front();
bVisitied[start.i][start.j] = true;
q.pop();
if (bEnd == true) {
//cout << endl;
break;
}
for (int i = 0; i < 8; i++) {
int tmpDiri = start.i+diri[i];
int tmpDirr = start.j+ dirj[i];
if (tmpDiri <= -1 || tmpDirr <= -1 || tmpDiri >= n || tmpDirr >= n) {
continue;
}
if (bVisitied[tmpDiri][tmpDirr] == false) {
bVisitied[tmpDiri][tmpDirr] = true;
Point tmpp;
tmpp.i = tmpDiri;
tmpp.j = tmpDirr;
tmpp.cnt = start.cnt + 1;
if (tmpDiri==end.i&&tmpDirr==end.j) {
i = 8;
//cout << endl;
//cout << tmpp.cnt<<endl<<endl;
gCount.push_back(tmpp.cnt);
bEnd = true;
}
q.push(tmpp);
//Prints(bVisitied, n, n);
}
}
}
if (bEnd == false) {
gCount.push_back(0);
//cout << 0;
}
}
for (int i = 0; i < gCount.size(); i++) {
cout << gCount[i] << endl;
}
return 0;
}