7562번 나이트의 이동

 기본적인 BFS문제.

 

 위, 아래, 왼쪽, 오른쪽으로 움직이던 기존 문제들과는 달리 이번에는 8개의 방향으로 움직인다. 이 표시만 잘해주고 BFS 돌려주면 해결!

 

#include <iostream>
#include <algorithm>
#include <queue>
#define visited true
#define Non_visited false
#define MAX 301
 
using namespace std;
 
typedef pair<int,int> pir;
int xx[8]={1,2,2,1,-1,-2,-2,-1};
int yy[8]={2,1,-1,-2,-2,-1,1,2};
bool Check[MAX][MAX];
int cnt[MAX][MAX];
int num;
int k,x,y,targetX,targetY;
queue<int> ans;
 
void solved(){
    queue<pir> p;
    p.push(pir(y,x));
    Check[y][x]=visited;
    
    while(!p.empty()){
        int y=p.front().first;
        int x=p.front().second;
        p.pop();
        
        if(targetX==x && targetY==y){
            ans.push(cnt[y][x]);
            break;
        }
 
        for(int i=0;i<8;i++){
            int ny=y+yy[i];
            int nx=x+xx[i];
            
            if(ny<0 || nx<0 || ny>=k || nx>=k) continue;
            if(Check[ny][nx]!=visited){
                p.push(pir(ny,nx));
                Check[ny][nx]=visited;
                cnt[ny][nx]=cnt[y][x]+1;
            }
        }
    }
}
 
void Clear(){
    for(int i=0;i<k;i++){
        for(int j=0;j<k;j++){
            cnt[i][j]=0;
            Check[i][j]=Non_visited;
        }
    }
}
 
int main(){
    cin >> num;
    
    while(num--){
        cin >> k >> y >> x >> targetY >> targetX;
        solved();
        Clear();
//        fill(Check,Check+k,Non_visited);
    }
    
    while(!ans.empty()){
        int x=ans.front();
        ans.pop();
        
        cout << x << endl;
    }
}