[백준 16509] 장군

https://www.acmicpc.net/problem/16509

16509번: 장군

#include <cstdio>
#include <queue>
#include <cstring>
int sr, sc;
int kr, kc;

int board[10 + 2][10 + 2];
struct _st
{
	int x, y;
};
std::queue<_st> Q;
int visited[10 + 2][10 + 2];


void debug()
{
	for (int i = 0; i <= 9; i++) {
		for (int j = 0; j <= 8; j++) {
			printf("%3d", visited[i][j]);
		}
		printf("\n");
	}
}



void input()
{
	scanf("%d %d", &sr, &sc);
	scanf("%d %d", &kr, &kc);
}




int BFS()
{
	// 상 하 좌 우
	int dir_x[4] = { -1, 1, 0, 0 };
	int dir_y[4] = { 0, 0 , -1, 1 };
	int move[4][2][2] = {
		{{-2, -2}, {-2, 2}},
		{{ 2, -2}, {2, 2}},
		{{-2, -2}, {2, -2}},
		{{-2, 2}, {2, 2}} };
	
	int chk[4][2][2] = { 
		{{-1, -1}, {-1, 1}},
		{{1, -1}, {1, 1}},
		{{-1, -1}, {1, -1}}, 
		{{-1, 1}, {1, 1}}};

	memset(visited, -1, sizeof(visited));

	Q.push({ sr, sc });
	visited[sr][sc] = 0;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.x == kr && data.y == kc) return visited[kr][kc];


		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];
			if (nx < 0 || nx > 9 || ny < 0 || ny > 8) continue;

			for (int d = 0; d < 2; d++) {
				int dx = nx + move[p][d][0];
				int dy = ny + move[p][d][1];

				if (dx < 0 || dx > 9 || dy < 0 || dy > 8) continue;
				if (nx + chk[p][d][0] == kr && ny + chk[p][d][1] == kc) continue;
				if (visited[dx][dy] >= 0) continue;
				Q.push({ dx, dy });
				visited[dx][dy] = visited[data.x][data.y] + 1;
			}
		}
	}
	return -1;
}


int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

가는 길에 기물 있는지 신경써주기 !