[C++] 6146 : 신아를 만나러

문제 📝

6146 : 신아를 만나러

입력 ✏️

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

출력 💻

11

문제해결법 💭

일반적인 BFS문제로 생각 된다.
웅덩이의 X, Y의 입력값이 -500 ~ 500 까지 라서 범위설정과 X, Y를 어떻게 변환 할지가 중요하다

소스코드 ⌨️

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

#define X first
#define Y second
int stx, sty, n;
int dist[1002][1002];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int cheak_i(int n) {
	if (n < 0) n = 501 + n;
	else n += 501;
	return n;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> stx >> sty >> n;

	stx = cheak_i(stx);
	sty = cheak_i(sty);

	for(int i = 1; i < 1002; i++) {
		fill(dist[i], dist[i] + 1002, -1);
	}
	//(-500, -500) = dist[1][1] /  (0, 0) = dist[501][501] , (-4, -4) = dist[497][497] / (500, 500) = dist[1001][1001]
	int x = 0, y = 0;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		x = cheak_i(x);
		y = cheak_i(y);
		dist[x][y] = 0;
	}
	queue<pair<int, int>> que;
	que.push({ 501, 501 });
	dist[501][501] = 0;
	while (!que.empty()) {
		pair<int, int> cur = que.front(); que.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx > 1002 || ny < 0 || ny > 1002) continue;
			if (dist[nx][ny] != -1) continue;
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			que.push({ nx, ny });
			if (nx == stx && ny == sty) {
				while (!que.empty())
					que.pop();
				cout << dist[nx][ny];
				break;
			}
		}
	}
}