메모리
시간
1264 KB
0 ms
Code
#include <cstdio>
#include <queue>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int map[200][200] = {0,};
int result;
int r1,c1,r2,c2;
scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
queue <pair<int, int> > queue;
int mov_r[6] = {-2, -2, 0, 0, 2, 2};
int mov_c[6] = {-1, 1, -2, 2, -1, 1};
queue.push(make_pair(r1,c1));
while (!queue.empty())
{
result = 0;
for (int i = 0; i < 6; i++)
{
int rr = queue.front().first + mov_r[i];
int cc = queue.front().second + mov_c[i];
if(rr >= 0 && rr < n && cc >= 0 && cc < n)
{
if (map[rr][cc])
continue ;
map[rr][cc] = map[queue.front().first][queue.front().second] + 1;
if (rr == r2 && cc == c2)
{
printf("%d", map[rr][cc]);
return 0;
}
queue.push(make_pair(rr,cc));
}
}
queue.pop();
}
printf("%d", -1);
return 0;
}
C++
복사
문제 풀이
체스판에서 r, c 가 이동할 수 있는 경우는 총 6가지가 있다.
mov_r , mov_c 배열을 사용하여 인덱스를 움직여주고 queue<pair> 를 사용해서 방문한 인덱스 체크와 counting 을 함께 해주었다.
만약 움직일 수 있는 다음칸이 체스판 내에 있다면 방문여부를 체크 후 움직인 칸에 count + 1 을 헤주고
만약 도달해야할 칸에 도달 했다면 해당 값 출력을 한다.
만약 다음 방문할 칸이 체스판 범위를 넘어가면 continue , 큐에 넣지 않고 다음 칸을 체크한다.
큐에 값이 비었다면 해당 칸에 갈 수 없음으로 -1 출력을 한다.