백준[7562] 나이트의 이동

별다른 문제없이 해결했지만.. 초기화를 할 때 범위를 300이 아닌 301로 지정하여 수십 번 틀렸다..ㅠ

 

이차원상의 이동을 하는 문제는 이동가능한 범위를 배열로 나타내어 문제를 풀면 쉽게 풀 수 있다.

최단 거리를 찾는 문제들은 bfs를 사용하면 문제를 해결할 수 있는 것 같다.

 

#include <bits/stdc++.h>

int testCase;
int length;
int finalX, finalY; //최종 도착지
int mvCount;
bool knightVisited[301][301] = {false};
int knightCount[301][301];

void printLocate();
void printVisited();

void knightBFS(int x,int y){
    queue<pair<int, int>> knightQ;

    knightQ.push(make_pair(x, y));
    knightVisited[x][y] = true;

    int dX[8] = {1,-1,1,-1,-2,-2,2,2};
    int dY[8] = {2,2,-2,-2,1,-1,1,-1};

    int mvX,mvY;

    while(!knightQ.empty()){
        mvX = knightQ.front().first;
        mvY = knightQ.front().second;
        knightQ.pop();

        if(mvX== finalX && mvY==finalY){
            while(!knightQ.empty()){
                knightQ.pop();
            }
            break;
        }

        for(int i=0;i<8;i++){
            int mx = mvX + dX[i];
            int my = mvY + dY[i];

            if(mx<0 || mx> length-1 || my<0 || my>length-1 || knightVisited[mx][my])
                continue;

            if(!knightVisited[mx][my]){
                knightVisited[mx][my] = true;
                knightCount[mx][my] = knightCount[mvX][mvY] + 1;
                knightQ.push({mx,my});
            }

        }
    }
    mvCount = knightCount[finalX][finalY];
}



void mvKnight(){
    cin>>testCase;

    for(int i=0;i<testCase;i++){
        cin>>length;
        int x,y;
        cin>>x>>y;
        cin>>finalX>>finalY;
        knightBFS(x,y);
        cout<<mvCount<<endl;

        fill(&knightCount[0][0], &knightCount[300][300], 0);
        fill(&knightVisited[0][0], &knightVisited[300][300], false);

    }
}