나이트의 이동_백준7562

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

7562번: 나이트의 이동

큐에 나이트가 이동할 수 있는 경우를 모두 입력하고 입력받은 순서대로 다음으로 이동 가능한 경우를 큐의 제일 뒤에 계속 넣다가 원하는 좌표에 도착한 경우가 있다면 그곳의 깊이가 최소 이동횟수이다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;


int zx[8] = {-1,-2,-2,-1,1,2,2,1};
int zy[8] = {-2,-1,1,2,2,1,-1,-2};


int n, m,x,y,v;

void bfs(int a, int b){
	queue<int> qx;
	queue<int> qy;
	queue<int> cnt;
	int ck[301][301]={0};
	int cn, xx, yy;
	ck[a][b] = 1;
	qx.push(a);
	qy.push(b);
	cnt.push(0);
	while(true){
		xx = qx.front();
		yy = qy.front();
		cn = cnt.front();
		if(xx == x && yy == y){
			printf("%d\n",cn);
			return;
		}
		qx.pop();
		qy.pop();
		cnt.pop();
		for(int i = 0; i < 8; i++){
			int kx = xx+zx[i];
			int ky = yy+zy[i];
			if(kx >= 0 && kx < m && ky >= 0 && ky < m && ck[kx][ky] == 0){
				ck[kx][ky] = 1;
				qx.push(kx);
				qy.push(ky);
				cnt.push(cn+1);
			}
		}
	}
}



int main()
{
	int a,b;
	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		scanf("%d",&m);
		scanf("%d%d",&a,&b);
		scanf("%d%d",&x,&y);
		bfs(a,b);
	}

	
	return 0;
}