Baekjoon 17290 Crazy_aRcade_Good

Link https://www.acmicpc.net/problem/17290

소스결과 1998 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 구현

 

설명

물폭탄이 터져도 살아 남을 수 있는 위치까지의 거리를 출력하자.

 

알고리즘

1. 초기 상태를 가지고 물폭탄의 위치를 queue에 저장한다.

2. 물폭탄 queue에서 물폭탄을 꺼내면서 초기 2차원 배열을 업데이트한다.

3. 플레이어의 위치를 기준으로 BFS를 통해 가장 가까운 위치를 구한다.

 

소스코드

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

const short MAX = 10;

bool board[MAX][MAX];
int posX[] = { 1, 0, -1, 0 };
int posY[] = { 0, 1, 0, -1 };

struct Point {
	short x, y;

	Point() {};
	Point(short x, short y) : x(x), y(y){}
};

int main()
{
	int x, y; cin >> x >> y;
	x--; y--;

	char input[MAX][MAX + 1] = {};
	queue<Point> q;

	for (int i = 0; i < MAX; i++)
		cin >> input[i];

	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
		{
			if (input[i][j] == 'o') {
				q.push(Point(i, j));
			}
		}

	while (!q.empty())
	{
		Point cur = q.front(); q.pop();

		for (int i = 0; cur.x + i < 10; i++) 
			board[cur.x + i][cur.y] = true;

		for (int i = 0; cur.x - i >= 0; i++)
			board[cur.x - i][cur.y] = true;

		for (int i = 0; cur.y + i < 10; i++)
			board[cur.x][cur.y + i] = true;

		for (int i = 0; cur.y - i >= 0; i++) {
			board[cur.x][cur.y - i] = true;
		}
		
	}

	queue<Point> save;

	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			if (!board[i][j])
				save.push(Point(i, j));

	int res = 21;

	while (!save.empty()) {
		Point cur = save.front(); save.pop();

		int dis = abs(x - cur.x) + abs(y - cur.y);

		if (res > dis)
			res = dis;
	}

	cout << res;

	return 0;
}