정올 장기
/*
N×M장기판에 졸 한개와 말 한개가 놓여 있다.말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다.
말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자.
첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다.(1≤N, M≤100)
둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다.
단, 장기판의 제일 왼쪽 위의 위치가(1, 1)이다.
각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다.
말이 졸을 잡기 위한 최소 이동 횟수를 출력한다.
[Copy]
9 9
3 5 2 8
[Copy]
2
*/
#include <stdio.h>
typedef struct {
int sero;
int garo;
int idx;
} _position;
_position POSITION[1000000];
int main()
{
int garo = 0; // 세로
int sero = 0; // 가로
int mal_sero = 0; // 말의 세로
int mal_garo = 0; // 말의 가로
int jol_sero = 0;
int jol_garo = 0;
scanf("%d %d", &sero, &garo);
scanf("%d %d", &mal_sero, &mal_garo);
scanf("%d %d", &jol_sero, &jol_garo);
int head = 0;
int tail = 1;
int Dy[] = { 2, 1, -1, -2, 2, 1, -1, -2 };
int Dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int map[102][102] = { 0, };
int tmp_sero = 0;
int tmp_garo = 0;
POSITION[0].sero = mal_sero;
POSITION[0].garo = mal_garo;
POSITION[0].idx = 0;
while (1)
{
for (int i = 0; i < 8; i++)
{
tmp_sero = POSITION[head].sero + Dy[i];
tmp_garo = POSITION[head].garo + Dx[i];
if (tmp_sero >= 1 && tmp_sero <= sero && tmp_garo >= 1 && tmp_garo <= garo)
{
if (map[tmp_sero][tmp_garo] == 0)
{
if (tmp_garo == jol_garo && tmp_sero == jol_sero)
{
printf("%d\n", POSITION[head].idx + 1);
return 0;
}
POSITION[tail].sero = tmp_sero;
POSITION[tail].garo = tmp_garo;
POSITION[tail].idx = POSITION[head].idx + 1;
tail++;
map[tmp_sero][tmp_garo] = 1;
}
}
}
head++;
}
return 0;
}