[BOJ]7562夜移動(BFS)

1.質問

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

2.アイデア

最短経路を探す問題なので、幅優先ナビゲーション(BFS)を使用します.

3.解法

1) 🕚ランタイムエラー🕚

コード

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

#define MAX 300
int board[MAX][MAX]; // 현재 위치까지 이동횟수 저장
int visited[MAX][MAX];
queue<pair<int, int>> q;
int departureX, departureY, destinationX, destinationY;
int len; // len : 체스판 한 변의 길이

int dx[8] = { -2,-2,-1,-1,1,1,2,2 };
int dy[8] = { 1,-1,2,-2,2,-2,1,-1 };

void BFS(int x, int y) {
	visited[x][y] = 1;
	q.push(make_pair(x, y));

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (x == destinationX && y == destinationY) // 도착 지점에 도달하면 출력하고 끝낸다
		{
			cout << board[x][y] << '\n';
			break;
		}

		for (int i = 0; i < 8; ++i) // 8가지 방향을 탐색한다.
		{
			int nextx = x + dx[i];
			int nexty = y + dy[i];

			if (nextx < 0 || nexty < 0 || nextx >= len || nexty >= len) continue;
			if (visited[nextx][nexty] == 0) // 아직 방문하지 않았다면 탐색한다.
			{
				visited[nextx][nexty] = 1;
				q.push(make_pair(nextx, nexty));
				board[nextx][nexty] = board[x][y] + 1;
			}
		}

	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int testcase;
	cin >> testcase;

	while(testcase--)
	{
		cin >> len;
		cin >> departureX >> departureY >> destinationX >> destinationY;

		BFS(departureX, departureY);

		/* 다음 testcase를 위해 체스판, visited, queue, 이동횟수 초기화*/
		for (int i = 0; i < len; ++i)
			for (int j = 0; i < len; ++j)
			{
				board[i][j] = 0;
				visited[i][j] = 0;
			}
		while (!q.empty()) q.pop();
	}
}

エラー原因

2) ⭕RIGHT⭕

コード

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

#define MAX 301

int L;
int start_x, start_y, dst_x, dst_y;
int visited[MAX][MAX] = { 0 };
int path[MAX][MAX] = { 0 };
int dx[8] = { -2,-2,-1,-1,1,1,2,2 };
int dy[8] = { 1,-1,2,-2,2,-2,1,-1 };
queue<pair<int, int>> q;

void BFS(int cur_x, int cur_y) {
	visited[cur_x][cur_y] = 1;
	q.push(make_pair(cur_x, cur_y));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (x == dst_x && y == dst_y) break;

		for (int i = 0; i < 8; ++i) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];

			if (next_x < 0 || next_x >= L || next_y < 0 || next_y >= L)
				continue;

			if (visited[next_x][next_y] == 0) {
				visited[next_x][next_y] = 1;
				q.push(make_pair(next_x, next_y));
				path[next_x][next_y] = path[x][y] + 1;
			}
		}
	}
}

void initialize() {
	// BFS에 사용된 배열과 큐 초기화
	for(int i=0;i<L;++i)
		for (int j = 0; j < L; ++j) {
			visited[i][j] = 0;
			path[i][j] = 0;
		}
	while (!q.empty())
		q.pop();
}

int main() {
	int num_of_testcase;
	cin >> num_of_testcase;

	while (num_of_testcase--) {
		cin >> L;
		cin >> start_x >> start_y >> dst_x >> dst_y;

		BFS(start_x, start_y);

		cout << path[dst_x][dst_y] << '\n';

		initialize();
	}
	return 0;
}

その他の説明

int dx[8] = { -2,-2,-1,-1,1,1,2,2 };
int dy[8] = { 1,-1,2,-2,2,-2,1,-1 };

現在の位置で移動できる場所.

<コメント>
ブログ1 ラーニングリポジトリ
ブログ2 ペンギンとパソコン