[백준 알고리즘] 나이트의 이동.txt

//나이트의 이동

//1. 그냥 방향타만 바꾸면됌.
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef struct cell{
    int r,c;
    int count;
}Cell;

int rdir[8] = {-1,-2,-2,-1,1,2,2,1};
int cdir[8] = {-2,-1,1,2,2,1,-1,-2};

bool visit[303][303];
int result=0;

int main(){
    int test = 0;
    scanf("%d", &test);
    
    for(int t = 0; t<test; t++){
        Cell start;
        Cell target;
        int n;
        scanf("%d", &n);
        scanf("%d %d", &start.r, &start.c);
        scanf("%d %d", &target.r, &target.c);
        
        for(int i =0;i<n; i++){
            for(int j =0; j<n; j++){
                visit[i][j] = false;
            }
        }
        
        queue<Cell> root;
        root.push({start.r, start.c, 0});
        
        visit[start.r][start.c] = true;
        
        while(!root.empty()){
            Cell temp = root.front();
            root.pop();
            
           // printf("%d %d\n", temp.r, temp.c);
            
            if(temp.r== target.r && temp.c == target.c){
                result = temp.count;
            }
            else{
                for(int i=0; i<8; i++){
                    int nowR = temp.r + rdir[i];
                    int nowC = temp.c + cdir[i];
                    if(0<=nowR && nowR<n && 0<= nowC && nowC<n && visit[nowR][nowC] == false){
                        visit[nowR][nowC] = true;
                        root.push({nowR, nowC,temp.count+1});
                    }
                }
            }
        }
        while(!root.empty()){
            root.pop();
        }
        printf("%d\n", result);
    }
    
    return 0;
}