백준 16948번 데스나이트

1919 단어 백준BFSBFS

문제 링크

코드 설명

기본적인 BFS 탐색 방법이다. map에 직접 카운트를 해주는 방식진행하였다.
이후 도착지에 도착하면 break를 멈춰준후 카운트를 출력해준다.

소스 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int dx[] = { -2,-2,0,0,2,2 };
int dy[] = { -1,1,-2,2,-1,1 };
int N;
int map[201][201];
bool visited[201][201];
int target[4];
int cnt;
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (!visited[ny][nx]) {
				visited[ny][nx] = true;
				map[ny][nx] = map[y][x] + 1;
				q.push({ ny,nx });
			}

			if (ny == target[3] && nx == target[2]) {
				cnt = map[ny][nx];
			}

		}
	}
	if (cnt == 0) cnt = -1;
}

int main() {
	cin >> N;
	for (int i = 0; i < 4; i++) {
		cin >> target[i];
	}
	bfs(target[1], target[0]);

	cout << cnt;
	return 0;
}

좋은 웹페이지 즐겨찾기