알고리즘 문제
[C/C++ 백준 7562번] 나이트의 이동 (Silver 2)
새파란 공대생
2020. 10. 18. 03:28
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 ��
www.acmicpc.net
기초적인 bfs 문제이다. 나이트가 갈 수 있는 모든 점을 queue를 이용해 가주자!
#include <cstdio>
#include <queue>
using namespace std;
bool visit[333][333];
int depth[333][333], l;
int xmove[8]={-2,-1,1,2,2,1,-1,-2};
int ymove[8]={1,2,2,1,-1,-2,-2,-1};
void bfs(pair <int, int> p1, pair <int, int> p2){
queue <pair <int, int>> q;
q.push(p1);
visit[p1.first][p1.second] = true;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
if(x==p2.first && y==p2.second){
printf("%d\n", depth[x][y]);
break;
}
q.pop();
for(int i=0; i<8; i++){
int xn = x+xmove[i];
int yn = y+ymove[i];
if(xn>=0 && xn<l && yn>=0 && yn<l){
if(!visit[xn][yn]){
visit[xn][yn] = true;
depth[xn][yn] = depth[x][y]+1;
q.push({xn, yn});
}
}
}
}
}
int main(void){
int T;
scanf("%d", &T);
for(int i=0; i<T; i++){
int x1, y1, x2, y2;
scanf("%d", &l);
for(int i=0; i<l; i++){
for(int j=0; j<l; j++){
visit[i][j] = false;
depth[i][j] = 0;
}
}
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
pair <int, int> p1 = make_pair(x1, y1);
pair <int, int> p2 = make_pair(x2, y2);
bfs(p1, p2);
}
}