장기(BFS)

문제 설명

---

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)이다.

출력 설명

---

말이 졸을 잡기 위한 최소 이동 횟수를 출력한다.

입력 예시

---

9 9
3 5 2 8

출력 예시

---

2

#include <stdio.h>
#include <string.h>
#define MAXNM (100)
int N, M;//장기판 행의 수, 열의 수
int R, C, S, K;//말 행과 열, 졸 행과 열
 
int visited[MAXNM+10][MAXNM+10];
struct QUE{
    int n, m, t;
};
 
struct QUE que[MAXNM * MAXNM + 10];
int wp, rp;
 
void push(int n, int m, int t){
    if ((n<1)||(n>N)||(m<1)||(m>M)) return;
    if (visited[n][m]) return;
    visited[n][m]=1;
    que[wp].n=n; que[wp].m=m; que[wp].t=t; wp++;
}
void pop(void){
    rp++;
}
struct QUE front(void){
    return que[rp];
}
int empty(void){
    return wp==rp;
}
 
int BFS(void){
    int dn[] = {-2, -2, -1, 1, 2, 2, 1, -1};
    int dm[] = {-1, 1, 2, 2, 1, -1, -2, -2};
    //0.초기화
    memset(visited, 0, sizeof(visited));
    wp = rp = 0;
    //1.시작위치 큐에 저장
    push(R, C, 0);
    //2.반복문
    while (!empty()){
        struct QUE cur = front(); pop();
        if ((cur.n==S) && (cur.m==K)) return cur.t;//성공
        for (int i=0; i<8; i++){
            push(cur.n+dn[i], cur.m+dm[i], cur.t+1);
        }
    }
    //3.실패(이 문제는 이런 경우 없음)
    return -1;//디버깅을 위해...
}
 
void InputData(void){
    scanf("%d %d", &N, &M);
    scanf("%d %d %d %d", &R, &C, &S, &K);
}
 
int main(void){
    int ans = -1;
    InputData();//입력
 
    ans = BFS();//여기서부터 작성
 
    printf("%d\n", ans);//출력
    return 0;
}