백준 1600 말이 되고픈 원숭이 (bfs , 사선)

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

1600번: 말이 되고픈 원숭이

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>	
#include<string.h>	
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int K, W, H;
int map[205][205];
int visited[205][205][33];
//int dy[] = { 1,0,-1,0 };
//int dx[] = { 0,1,0,-1 };

int dx[] = { 0, 0, -1, 1, 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[] = { -1, 1, 0, 0, -2, -1, 1, 2, 2, 1, -1, -2 };
int res;
queue <pair<pair<int, int>,pair<int, int > > >  q;
void bfs() {
	
	while (!q.empty()) {
		int cx = q.front().first.first;
		int cy = q.front().first.second;
		int ck = q.front().second.first;
		int cnt = q.front().second.second;
		q.pop();

		if (cx == H - 1 && cy == W - 1) {
			res = cnt;
			break;
		}

		for (int i = 0; i < 12; i++) {

				int nx = cx + dx[i];
				int ny = cy + dy[i];

				if (nx >= 0 && ny >= 0 && nx < H && ny < W && map[nx][ny] == 0) {
					
					if (ck < K) {
						if (i <= 3 && visited[nx][ny][ck] == 0) { //상하좌우라면 
							visited[nx][ny][ck] = 1;
							q.push(make_pair(make_pair(nx, ny), make_pair(ck, cnt + 1)));
						}
						if (i > 3 && visited[nx][ny][ck + 1] == 0) { //말이라면 
							visited[nx][ny][ck + 1] = 1;
							q.push(make_pair(make_pair(nx, ny), make_pair(ck + 1, cnt + 1)));
						}

					}
					else if (ck >= K) { //무조건 상하좌우
						if (i <= 3 && visited[nx][ny][ck] == 0) { //상하좌우라면 
							visited[nx][ny][ck] = 1;
							q.push(make_pair(make_pair(nx, ny), make_pair(ck, cnt + 1)));
						}
					}
				}

			
		}
	}
}

int main() {
	scanf("%d", &K);
	scanf("%d%d", &W,&H);
	for (int i = 0; i < H; i++) { //행 
		for (int j = 0; j < W; j++) { //열 
			scanf("%d", &map[i][j]);
		}
	}
	res = -1;
	for (int i = 0; i < 30; i++) {
		visited[0][0][i] = 1;
	}
	q.push(make_pair(make_pair(0, 0), make_pair(0, 0)));
	bfs();
	printf("%d", res);
	return 0;
}

ㅡㅡㅡㅡ