7562 나이트의 이동

나이트의 이동

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	11424	5003	3788	43.904%

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 몇 번만에 이동할 수 있는지 출력한다.

BFS문제이다.

각 단계를 출력하면된다. 발상을 헷갈려서 시간을 50분이나 허비했다.

심지어  풀었으나 속도가 느리게 나왔다. 최적화를 해야한다.

#include <bits/stdc++.h>

using namespace std;

struct Pair{

int x;

int y;

};

int l=0;

int board[301][301];

bool checked[301][391];

int x_direction[8] = {-1,-2,-2,-1, +1,+2,+2,+1};

int y_direction[8] = {-2,-1,+1,+2, -2,-1,+1,+2};

queue<Pair> que;

int bfs(int x2, int y2);

int main(){

freopen("input.txt","r",stdin);

ios::sync_with_stdio(false);

cin.tie(0);

int T;

cin>>T;

int x1,y1,x2,y2;

for(int t=0; t<T; ++t){

memset(board, 0, sizeof(board));

memset(checked, false, sizeof(checked));

que = queue<Pair>();

cin>>l;

cin>>x1>>y1;

cin>>x2>>y2;

que.push({x1,y1});

checked[x1][y1] = true;

cout<<bfs(x2,y2)+1<<"\n";

}

return 0;

}

int bfs(int x2, int y2){

int one_step_temp =que.size();

int total_step = 0;

Pair p;

int j=0;

while(!que.empty()){

one_step_temp = que.size(); // 이 발상 반드시 기억하자

for(int i=0 ; i<one_step_temp; ++i){

p = que.front();

que.pop();

for( j=0; j<8; ++j ){

if( (p.x+x_direction[j] >= 0 && p.x+x_direction[j]<l) &&

(p.y+y_direction[j] >= 0 && p.y+y_direction[j]<l) &&

!checked[p.x+x_direction[j]][p.y+y_direction[j]]

){

que.push({p.x+x_direction[j],p.y+y_direction[j]});

checked[p.x+x_direction[j]][p.y+y_direction[j]] = true;

if( x2 == p.x+x_direction[j] && y2 == p.y+y_direction[j] ){

return total_step;

}

}

}

}

total_step++;

}

return -1;

}