장기2

N×M장기판에 졸 한개와 말 한개가 놓여 있다.
말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다. 
말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자

---

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Knight {
    int r, c, moves;
};

int main() {
  
    int N, M;
    cin >> N >> M;

    int kr, kc, jr, jc;
    cin >> kr >> kc >> jr >> jc;

    int dr[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };
    int dc[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };

    vector<vector<bool>> visited(N + 1, vector<bool>(M + 1, false));

    queue<Knight> q;
    q.push({ kr, kc, 0 });
    visited[kr][kc] = true;

    int answer = -1;

    while (!q.empty()) {
        Knight current = q.front();
        q.pop();

        if (current.r == jr && current.c == jc) {
            answer = current.moves;
            break;
        }

        for (int i = 0; i < 8; i++) {
            int nr = current.r + dr[i];
            int nc = current.c + dc[i];

            if (nr >= 1 && nr <= N && nc >= 1 && nc <= M) {
                if (!visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.push({ nr, nc, current.moves + 1 });
                }
            }
        }
    }

    cout << answer << "\n";

    return 0;
}

처음에 장기판의 크기를 정하고 각 말에 시작 좌표와 목표좌표를 입력 

그후 장기말이 이동 할수 있는 8가지 방향의 좌표 변화량을 배열로 정의 

이미 좌표를 다시 방문하여 무한루프를 방지 

 

q를 이용해 출발점에서 가까운 곳부터 차례로 탐색 한다.

그후 말의 시작 위치와 이동횟수에 0을 넣고 시작위치를 방문 처리 한다.

anser은 최종 정답을 저장할 변수로 실패를 대비해 -1로 초기화 한다.

 

while을 이용해서 경로가 없어질때 까지 계속 반복 하여 큐의 맨앞에 현위치의 말의 정보를 가져온다.

꺼낸 말의 위차가 졸의 위치와 일치 한다면 현재까지의 이동 횟수가 최단 거리 이므로 answer에 저장 후 루프 탈출

 

그후 for문을 이용하여 현재 위치에서 말이 갈수 있는 다음 위치 계산 후 계산한 위치가 격자 내부 인지 확인후 

아직 방문 하지 않았다면 방문 표시한후 이동 횟수 +1 한다. 그후 출력한뒤 종료함